#include<stdio.h>
long a[100001],x,n,m,i,c;
long cb0(long st,long dr);
long cb1(long st,long dr);
long cb2(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(;m;m--)
        { scanf("%ld%ld",&c,&x);
          if(c==1){printf("%ld",cb1(1,n));continue;}
          if(c==2){printf("%ld",cb2(1,n));continue;}
          printf("%ld",cb0(1,n));
        }
        return 0;
}
long cb0(long st,long dr)
{
        long mid;
        if(dr-st>1)
        { mid=(st+dr)/2;
          if(a[mid]<=x)return cb0(mid,dr);
          return cb0(st,mid);
        }
        if(a[dr]==x)return dr;
        if(a[st]==x)return st;
        return -1;
}
long cb1(long st,long dr)
{       long mid;
        if(dr-st>1)
        { mid=(st+dr)/2;
          if(a[mid]<=x)return cb1(mid,dr);
          return cb1(st,mid);
        }
        if(a[dr]<=x) return dr;
        return st;
}
long cb2(long st,long dr)
{       long mid;
        if(dr-st>1)
        { mid=(st+dr)/2;
          if(a[mid]>=x) return cb2(st,mid);
          return cb2(mid,dr);
        }
        if(a[st]>=x)return st;
        return dr;
}