#include<stdio.h>
long a[100003],n,m,i,x,q,j,mid;
long zero(long st, long dr);
long unu(long st, long dr);
long doi(long st, long dr);
int main()
{   freopen("cautbin.in","r",stdin); freopen("cautbin.out","w",stdout);
    scanf("%ld",&n);
    for(i=1;i<=n;i++) scanf("%ld",&a[i]);
    scanf("%ld",&m);
    for(i=1;i<=m;i++)
    {      scanf("%ld%ld",&q,&x);
           if(q==0){ printf("%ld\n",zero(1,n+1)); continue;}
           if(q==1){ printf("%ld\n",unu(1,n+1)); continue;}
           printf("%ld\n",doi(1,n)); continue;
     }
    return 0;
}
long zero(long st, long dr)
{    while(dr-st-1)
     { mid=st+(dr-st)/2;
       if(a[mid]>x){ dr=mid; continue;}
       st=mid;
       }
     if(a[dr]==x) return dr;
     if(a[st]==x) return st;
     return -1;

}
long unu(long st, long dr)
{    while(dr-st-1)
     { mid=st+(dr-st)/2;
       if(a[mid]>x){ dr=mid; continue;}
       st=mid;
     }
     return st;
}
long doi(long st, long dr)
{  while(dr-st-1)
     { mid=st+(dr-st)/2;
       if(a[mid]<x){ st=mid; continue;}
       dr=mid;
     }
     return dr;
}