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