#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
 ifstream f("cautbin.in");
 ofstream g("cautbin.out");
int v[100000],n,x,m,i,K,t,k;
int main ()
{
    int i,c,x;
	int *it;
	f>>n;
	for(i=0;i<n;i++) f>>v[i];
	f>>m;
	for(i=0;i<m;i++)
        {
		f>>c>>x;
		if(c==0){
			it=upper_bound(v,v+n,x);
			it--;
			if(*it==x) g<<it-v+1;
			else  g<<-1;
		}
		else if(c==1){
			it=upper_bound(v,v +n,x);
			it--;
			g<<it-v+1;
		}
		else{
			it=lower_bound(v,v+n,x);
			g<<it-v+1;
		}
		g<<"\n";
	}
}