#include<fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int i,j,y,x,mij,li,ls,m,n,a[100001];
int main()
{f>>n;
for(i=1;i<=n;++i)
	f>>a[i];
f>>m;
for(i=1;i<=m;++i)
{f>>x>>y;
if(x==0)
{li=1;
ls=n;
while(li<=ls)
{mij=(li+ls)/2;
if(a[mij]==y&&a[mij+1]!=y)
	break;
else
	if(a[mij]>y)
		ls=mij-1;
	else
		li=mij+1;
}
if(li>ls)
	g<<"-1";
else
	g<<mij;
g<<'\n';
}
else
	if(x==1)
	{li=1;
	ls=n;
	while(li<ls)
	{mij=(li+ls)/2;
	if(a[mij]<=y)
		li=mij+1;
	else
		ls=mij;
	}
	mij=(li+ls)/2;
	if(a[mij]>y)
		--mij;
	g<<mij<<'\n';
	}
	else
	{li=1;
	ls=n;
	while(li<ls)
	{mij=(li+ls)/2;
	if(a[mij]<y)
		li=mij+1;
	else
		ls=mij;
	}
	mij=(li+ls)/2;
	if(a[mij]<y)
		++mij;
	g<<mij<<'\n';
	}
}
f.close();
g.close();
return 0;
}