#include<stdio.h>
#define N 100001

void citire(),rezolva(long,long);
long n,m,a[N];

int main (){
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    citire();
    return 0;
}

void citire(){
long x,y,i;
     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",&x,&y);
	rezolva(x,y);
     }
}

void rezolva(long x,long y){
long s,d,mij,i;
     s=1;d=n;
     for (;s<=d;){
	   mij=(s+d)/2;
	   if (a[mij]==y)break;
	   else
	       if (a[mij]>y) d=mij-1;
	       else s=mij+1;
     }
     if (x==0 && a[mij]!=y) printf("%ld\n",-1);
     else
	 if (x==0) {for (;a[mij]==y;mij++);
			printf("%ld\n",mij-1);
			}
		else if (x==1){ for (;;mij--)
				if (a[mij]<=y) {printf("%ld\n",mij);break;}}
			else	for(;;mij++)
				if (a[mij]>=y) {printf("%ld\n",mij);break;}
}