#include <cstdio>
using namespace std;
int a[100001],n,m,caz,val,i;
int search0(int st, int sf)
{
	int mij=(st+sf+1)/2;
	if(sf==st){if(a[mij]==val){return st;}return -1;}
	if(val>=a[mij]){return search0(mij,sf);}
	if(val<a[mij]){return search0(st,mij-1);}
}
int search1(int st, int sf)
{
	int mij=(st+sf+1)/2;
	if(sf==st){return st;}
	if(val>=a[mij]){return search1(mij,sf);}
	if(val<a[mij]){return search1(st,mij-1);}
}
int search2(int st, int sf)
{
	int mij=(st+sf)/2;
	if(sf==st){return st;}
	if(val>a[mij]){return search2(mij+1,sf);}
	if(val<=a[mij]){return search2(st,mij);}
}
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);
	while(m--){
		scanf("%ld%ld",&caz,&val);
		if(caz==0){printf("%ld\n",search0(1,n));}
		if(caz==1){printf("%ld\n",search1(1,n));}
		if(caz==2){printf("%ld\n",search2(1,n));}
			  }
return 0;
}