#include<stdio.h>
#define N 100001
long bin(long v[N],long p,long q,long x,long y)
{long m=p+(q-p)/2;
if(p>q&&x==0)
       return -1;
if(v[m]==y)
       if(x==0||x==1)
              {while(v[m+1]==y)
                     m++;
              return m;}
       else
              {while(v[m-1]==y)
                     m--;
              return m;}                             
if(v[m]<y)
       if(y<v[m+1])
              if(x==1)
                     return m+1;
              else
                     if(x==2)
                            return m;
                     else
                            return bin(v,m+1,q,x,y);
       else
              return bin(v,m+1,q,x,y);
else
       if(v[m-1]<y)
              if(x==1)
                     return m;
              else
                     if(x==2)
                            return m-1;
                     else
                            return bin(v,p,m-1,x,y);
       else
              return bin(v,p,m-1,x,y);}

int main()
{long n,m,i,x[N],y[N],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",&x[i]);
       scanf("%ld",&y[i]);}
for(i=1;i<=m;i++)
       printf("%ld\n",bin(v,1,n,x[i],y[i]));
fclose(stdin);
fclose(stdout);
return 0;}