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

int main()
{long n,m,i,*x,*y,*v;
freopen("cautbin.in","r",stdin);
freopen("cautbin.out","w",stdout);
scanf("%ld",&n);
v=(long*)malloc(n*sizeof(long));
for(i=1;i<=n;i++)
       scanf("%ld",&v[i]);
scanf("%ld",&m);
x=(long*)malloc(m*sizeof(long));
y=(long*)malloc(m*sizeof(long));
for(i=1;i<=m;i++)
       {scanf("%ld",&x[i]);
       scanf("%ld",&y[i]);
       printf("%ld\n",bin(v,1,n,x[i],y[i]));}
free(x);
free(y);
fclose(stdin);
fclose(stdout);
return 0;}