#include <cstdio>
#include <cstring>

#define file_in "cautbin.in"
#define file_out "cautbin.out"

#define nmax 100101

int N,M;
int V[nmax];


int cautare0(int val){
	
	int i=1;
	int j=N;
	int mij,poz;
	while(i<=j){
		mij=(i+j)/2;
		if (V[mij]==val)
			return mij;
		if (V[mij]<=val) i=mij+1;
		else j=mij-1;
	}
	
	return -1;
}

int cautare1(int val){
	
	int i=1;
	int j=N;
	int mij,poz;
	while(i<=j){
		mij=(i+j)/2;
		if (V[mij]<=val){poz=mij; 
		i=mij+1;
		}
		else j=mij-1;
	}
	
	return poz;
}

int cautare2(int val){
	
	int i=1;
	int j=N;
	int mij,poz;
	while(i<=j){
		mij=(i+j)/2;
		if (V[mij]>=val){poz=mij;
		j=mij-1;
		}
		else i=mij+1;
	}

	return poz;
}



int main(){
	
	int i,tip,val;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d", &N);
	for (i=1;i<=N;++i)
		 scanf("%d", &V[i]);
	scanf("%d", &M);
	while(M--){
		scanf("%d %d", &tip, &val);
		if (tip==0) { printf("%d\n",cautare0(val)); continue; }
		if (tip==1) { printf("%d\n",cautare1(val)); continue; }
		if (tip==2) { printf("%d\n",cautare2(val)); continue; }
	}
	
	return 0;
	
}