#include <fstream>

using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");
int a [100000];


int search(int start,int end,int num,int oper)
{

	int mij = (end + start) / 2;

	if(start>end){
		if(oper==0)
			return -1;

		else if(oper==2)
		{
			int poz = end;
			while(a[poz]<num)
			{
				++poz;
			}
			return --poz;
		}

		else
		{
			int poz = start;
			while(a[poz]>num)
			{
				--poz;
			}
			return ++poz;
		}
	}

	if(a[start]==num) return start;
	if(a[end]==num)return end;
	if(a[mij]==num) return mij;

	return (num > a[mij]) ? search(mij+1, end,num,oper) : search(start, mij-1,num,oper);

}


int main()
{
	int n,m,oper,poz,num;
	f>>n;

	for(int i=1;i<=n;++i)
	{
		f>>a[i];
	}

	f>>m;

	for(int i =1;i<=m;++i)
	{	
		f>>oper>>num; 
		poz = search(1,n,num,oper);
		g<<poz<<"\n";
	}

	return 0;
}