#include <iostream>
#include <fstream>

using namespace std;

long q,w,i,n,m,poz,x,v[100001]; 


void bin0(long beg, long end){
	if (beg==end){
		if (v[beg]==x) poz=beg;
		return;
	}
	if(v[(beg+end)/2+1]==x){
		poz=(beg+end)/2+1;
		bin0((beg+end)/2+1,end);
		return;
	}
	if(v[(beg+end)/2+1]<x){
		bin0((beg+end)/2+1,end);
		return;
	}
	if(v[(beg+end)/2+1]>x){
		bin0(beg,(beg+end)/2);
		return;
	}
}

void bin1(long beg, long end){
	if (beg==end){
		if (v[beg]<=x) poz=beg;
		return;
	}
	if(v[(beg+end)/2+1]<=x){
		poz=(beg+end)/2+1;
		bin1((beg+end)/2+1,end);
		return;
	}
	if(v[(beg+end)/2+1]>x){
		bin1(beg,(beg+end)/2);
		return;
	}
	
}
void bin2(long beg, long end){
	if (beg==end){
		if (v[beg]>=x) poz=beg;
		return;
	}
	if(v[(beg+end)/2]>=x){
		poz=(beg+end)/2;
		bin2(beg,(beg+end)/2);
		return;
	}
	if(v[(beg+end)/2]<x){
		bin2((beg+end)/2+1,end);
		return;
	}	
}


int main(){
	ifstream fin("cautbin.in");
	ofstream fout("cautbin.out");
		fin >> n;
		for (i=1; i<=n; i++){
			fin >> v[i];
		}
		fin >> m;
		for (w=1; w<=m; w++){
			poz=-1;
			fin >> q >> x;
			if (q==0){
				bin0(1,n);
				fout << poz << "\n";
			}
			if (q==1){
				bin1(1,n);
				fout << poz << "\n";
			}
			if (q==2){
				bin2(1,n);
				fout << poz << "\n";
			}
		}
	fin.close();
	fout.close();
}