#include<cstdio>
#include<algorithm>
using namespace std;
int n,i,m,k,v[100001],poz,x,t;
int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",&v[i]);
	scanf("%d",&m);
	for(i=1;i<=m;i++){
		scanf("%d %d",&t,&x);
		if(t==0){
			poz=upper_bound(v+1,v+n+1,x)-v-1;
			if(v[poz]==x)printf("%d\n",poz);
			else printf("-1\n");
		}
		else 
			if(t==1){
			poz=lower_bound(v+1,v+n+1,x+1)-v-1;
			printf("%d\n",poz);
			}
		else {
			poz=upper_bound(v+1,v+n+1,x-1)-v;
			printf("%d\n",poz);
		}
	}	
	return 0;
}