#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int N, M, i, m, nr, x, A[100002], p, u;
int main() {
	
	f>>N;
	for(i=1; i<=N; i++)
		f>>A[i];
	f>>M;
	for(i=1; i<=M; i++){
		f>>nr>>x;
		if (nr==0) {
			
			p=1; u=N;
			while (p<=u){
				m=p+(u-p)/2;
				if(A[m]>x)
					u=m-1;
				else
					p=m+1;
			}
			if(A[u]==x)
				g<<u<<"\n";
			else
				g<<"-1\n";
			
		}
		if (nr==1) {
			p=1; u=N;
			while (p<=u){
				m = p + (u-p)/2;
				if(A[m]<=x)
					p=m+1;
				else
					u=m-1;
			}
			g<<u<<"\n";
		}
		if (nr==2) {
			p=1; u=N;
			while (p<=u){
				m=p+(u-p)/2;
				if(A[m]>=x)
					u=m-1;
				else
					p=m+1;
			}
			g<<p<<"\n";
		}
	}
	f.close();
	g.close();
	return 0;
}