#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;
while(v[m]!=y||(p>q&&x==0))
       {if(v[m]<y)
               if(y<v[m+1])
                       if(x==2)
                              return m+1;
                       else
                              if(x==1)
                                      return m;
                              else
                                      return -1;
               else
                       {p=m+1;
                       m=p+(q-p)/2;}
       else
               if(v[m-1]<y)
                       if(x==2)
                              return m;
                       else
                              if(x==1)
                                      return m-1;
                              else
                                      return -1;
               else
                       {q=m-1;
                       m=p+(q-p)/2;}}
if(p>q&&x==0)
       return -1;
else
       if(x==0||x==1)
               {while(v[m+1]==y)
                       m++;
               return m;}
       else
               {while(v[m-1]==y)
                       m--;
               return m;}}

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;}