#include<fstream.h>
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
long n,m,a[100000],b[100000][2];
void cit()
{
	int i;
	fin>>n;
	for(i=1;i<=n;i++)
		fin>>a[i];//citim vectorul
	fin>>m;
	for(i=1;i<=m;i++)
		fin>>b[i][1]>>b[i][2];
}
int cautare(int li,int ls,int x)
{
	int j,i,k;
	i=li;
	j=ls;
	while(i<=j)
	{
		k=(i+j)/2;
		if(a[k]==x)
			return k;
		else
			if(a[k]>x)
				j=k-1;
			else
				i=k+1;
	}
	return k;	
}
int main()
{
	int k,i;
	cit();
	//k=cautare(1,n,3);
	for(i=1;i<=m;i++)
	{
		k=cautare(1,n,b[i][2]);
		
		if(b[i][1]==0)
		{while(a[k]==b[i][2])k++;
		k--;
			if(a[k]==b[i][2])
				fout<<k<<'\n';
			else
				fout<<"-1"<<'\n';
		}
		if(b[i][1]==1)
		{while(a[k]==b[i][2])k++;
		k--;
			if(a[k]<=b[i][2])
				fout<<k<<'\n';
			else
				fout<<k-1<<'\n';
		}
		if(b[i][1]==2)
		{while(a[k]==b[i][2])k--;
		
			if(a[k]>=b[i][2])
				fout<<k<<'\n';
			else
				fout<<k+1<<'\n';
		}
		//fout<<k<<'\n';
	}	
	return 0;
}