#include<stdio.h>
#define N 100001
long bin(long v[N],long p,long q,long x,long y)
{long m=p+(q-p)/2;
if(x==0&&p>q)
      return -1;
if(v[m]==y)
      if(x==0||x==1)
              {while(v[m+1]==y)
                       m++;
              return m;}
      else
              {while(v[m-1]==y)
                       m--;
              return m;}
if(v[m]<y)
      if(y<v[m+1])
              if(x==1)
                       return m+1;
              else
                       if(x==2)
                                return m;
                       else
                                return -1;
      else
              return bin(v,m+1,q,x,y);
else
      if(v[m-1]<y)
              if(x==1)
                       return m;
              else
                       if(x==2)
                                return m-1;
                       else
                                return -1;
      else
              return bin(v,p,m-1,x,y);}

int main()
{long n,m,i,x[N],y[N],v[N];
freopen("cautbin.in","r",stdin);
freopen("cautbin.out","w",stdout);
scanf("%ld",&n);
for(i=1;i<=n;i++)
       scanf("%ld",&v[i]);
scanf("%ld",&m);
for(i=1;i<=m;i++)
       {scanf("%ld",&x[i]);
       scanf("%ld",&y[i]);
       if(x[i]==1&&v[n]<y[i])
              printf("%ld\n",n);
       else
              if(x[i]==2&&v[1]>y[i])
                      printf("1\n");
              else
                      printf("%ld\n",bin(v,1,n,x[i],y[i]));}
fclose(stdin);
fclose(stdout);
return 0;}