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