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