#include<stdio.h>
long a[100003],n,m,i,x,q,j,mid;
long zero(long st, long dr);
long unu(long st, long dr);
long doi(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(i=1;i<=m;i++)
    {      scanf("%ld%ld",&q,&x);
           if(q==0){ printf("%ld\n",zero(1,n)); continue;}
           if(q==1){ printf("%ld\n",unu(1,n)); continue;}
           printf("%ld\n",doi(1,n)); continue;
     }
    return 0;
}
long zero(long st, long dr)
{    for(j=1;;j++)
     { if(dr-st==1) if(a[dr]!=x&&a[st]!=x) return -1;
       mid=st+(dr-st)/2;
       if(a[mid]==x){ while(a[mid]==a[mid+1]) mid++;
                      return mid;
                     }
       if(a[mid]>x){ dr=mid; continue;}
       if(a[mid]<x) st=mid;
     }
}
long unu(long st, long dr)
{    for(j=1;;j++)
     { if(dr-st==1){  if(a[dr]<=x) return dr;
                      return st;
                      }
       mid=st+(dr-st)/2;
       if(a[mid]==x){ while(a[mid]==a[mid+1]) mid++;
                      return mid;
                     }
       if(a[mid]>x){ dr=mid; continue;}
       if(a[mid]<x) st=mid;
     }
}
long doi(long st, long dr)
{   for(j=1;;j++)
     { if(dr-st==1){ if(a[st]>=x) return dr;
                      return dr;
                      }
       mid=st+(dr-st)/2;
       if(a[mid]==x){ while(a[mid]==a[mid+1]) mid++;
                      return mid;
                     }
       if(a[mid]>x){ dr=mid; continue;}
       if(a[mid]<x) st=mid;
     }
}