#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&&y<=v[i+1]&&i+1<=n)
        return i+1;
else
        if(v[i+1]<y&&i+2<=n)
               return i+2;
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>1&&v[i-step]>=y)
        i-=step;
if(v[i]>y&&y>=v[i-1]&&i-1>=1)
        return i-1;
else
        if(v[i-1]>y&&i-2>=1)
             return i-2;
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(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;}