#include<fstream>
#include<algorithm>
using namespace std;
int v[100001],i,j,n,p,m,u,x,k,s,nr,t;
int main()
{
	ifstream f("cautbin.in");
	ofstream g("cautbin.out");
	f>>n;
	for(i=1;i<=n;i++)
		f>>v[i];
	f>>nr;
	for (i=1;i<=nr;i++) {
		f>>t>>x;
		if (t==0) {
			p=1;u=n;
			while(p<=u)
			{
				m=(p+u)/2;
				if(v[m]<=x)
					p=m+1;
				else
					u=m-1;
			}
			if(v[u]==x)
				g<<u<<"\n";
			else
				g<<-1<<"\n";
			
			
		} else if (t==1) {
			p=1;u=n;
			while(p<=u)
			{
				m=(p+u)/2;
				if(v[m]<=x)
					p=m+1;
				else
					u=m-1;
			}
			g<<u<<"\n";
			
		} else
		if(t==2)
		{
			p=1;u=n;
			while(p<=u)
			{
				m=(p+u)/2;
				if(v[m]>=x)
					u=m-1;
				else
					p=m+1;
			}
			g<<p<<"\n";
		}
			
}
		

	
	
	return 0;
}