#include<stdio.h>
#define N 100001
long binar2(long v[N],long n,long y)
{long i,step;
for(step=1;step<n;step<<=1);
for(i=0;step;step>>=1)
if(i+step<n&&v[i+step]<=y)
        i+=step;
if(v[i]<y)
        return i+1;
return i;}

long binar1(long v[N],long n,long y)
{long i,step;
for(step=1;step<n;step<<=1);
for(i=n;step;step>>=1)
if(i-step>0&&v[i-step]>=y)
        i-=step;
if(v[i]>y)
        return i-1;
return i;}

long binar0(long v[N],long n,long y)
{long i,step;
for(step=1;step<n;step<<=1);
for(i=0;step;step>>=1)
if(i+step<n&&v[i+step]<=y)
        i+=step;
if(v[i]==y)
      return i;
return -1;}

int main()
{long n,m,i,x,y,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%ld",&x,&y);
       if(v[1]>y&&x==2)
              printf("1\n");
       else
              if(v[n]<y&&x==1)
                       printf("%ld\n",n);
              else
                       if(x==0)
                               printf("%ld\n",binar0(v,n,y));
                       else
                               if(x==1)
                                      printf("%ld\n",binar1(v,n,y));
                               else
                                      printf("%ld\n",binar2(v,n,y));}
fclose(stdin);
fclose(stdout);
return 0;}