#include<fstream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int main(){
	int n,i,v[100001],x,m,dr,st,cod,gasit,q,j;
	in>>n;
	for(i=1;i<=n;i++)
		in>>v[i];
	in>>q;
	for(j=1;j<=q;j++)
	{
		in>>cod>>x;
		st=1;
		dr=n;
		gasit=0;
		while(st<dr && gasit==0)
		{
			m=(st+dr)/2;
			if(x==v[m])
				gasit=1;
			else
				if(x>v[m])
					st=m+1;
				else
					dr=m-1;
		}
		if(cod==0)
		{
			if(gasit==1)
			{
				i=m;
				while(i<n && v[i+1]==x)
					i++;
				out<<i<<"\n";
			}
			else 
				out<<"-1\n";
		}
		else
			if(cod==1)
			{
				if(gasit==1)
				{
					i=m;
					while(i<n && v[i+1]==x)
						i++;
					out<<i<<"\n";
				}
				else
				{
					if(v[m]>x)
						m--;
					out<<m<<"\n";
				}
			}
			else
			{
				if(gasit==1)
				{
					i=m;
					while(i>1 && v[i-1]==x)
						i--;
					out<<i<<"\n";
				}
				else 
				{
					if(v[m]<x)
						m++;
					out<<m<<"\n";
				}
			}
	}
	return 0;
}