#include <fstream>
using namespace std;
int t,n,x,k,i,st,dr,mij,sol,v[100005];
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int main()
{	f>>n;
	for(i=1;i<=n;i++) f>>v[i];
	f>>t;
	while(t--)
	{	f>>k>>x;
		st=1; dr=n;
		if(k==0)
			{	sol=-1;
				while(st<=dr)
				{	mij=(st+dr)/2;
					if (v[mij]==x){sol=mij; st=mij+1; }
						else if (x<v[mij]) dr=mij-1;	else st=mij+1;
				}
				g<<sol<<"\n";
			}
		if (k==1)
			{	while(st<=dr)
				{	mij=(st+dr)/2;
					if(x<=v[mij]){sol=mij; st=mij+1;}
						else dr=mij-1;
				}
				g<<sol<<"\n";
			}
		if (k==2)
			{	while(st<=dr)
				{	mij=(st+dr)/2;
					if(v[mij]>=x){sol=mij; dr=mij-1;}
						else st=mij+1;
				}
				g<<sol<<"\n";
			}
	}
	return 0;
}