#include <iostream>
#include <fstream>

using namespace std;

int t,n,x,k,i,st,dr,mij,sol,v[100005];
	
    ifstream f("cautbin.in");
	ofstream g("cautbin.out");
int main()
{
	
	f>>n;
	for(i=1;i<=n;i++)f>>v[i];
	
	f>>t;
	
	for (i=1;i<=t;i++)
	{
		f>>k>>x;
		st=1;
		dr=n;
		sol=-1;
		if(k==0)
		{
			while(st<=dr)
			{
				mij=(st+dr)/2;
				if (v[mij]==x){sol=mij;st=mij+1;}else if (v[mij]>x) dr=mij-1;else st=mij+1;
			}
			g<<sol<<"\n";
		}
		if (k==1)
		{
			while(st<=dr)
			{
				mij=(st+dr)/2;
				if(v[mij]<=x){sol=mij;st=mij+1;}else dr=mij-1;
			}
			g<<sol<<"\n";
		}
		if (k==2)
		{
			while(st<=dr)
			{
				mij=(st+dr)/2;
				if(v[mij]>=x){sol=mij;dr=mij-1;}else st=mij+1;
			}
			g<<sol<<"\n";
		}
	}
	return 0;
}