#include<fstream>
#include<iostream>
#include<vector>
using namespace std;

typedef unsigned int uint32;

int BinSearch_0(vector<uint32>& v, uint32 val)
{
	int l=0,r=v.size()-1,pos=-1;
	while(l<=r)
	{
		const int index=l+((r-l)>>1);
		if(v[index]==val)
		{
			pos=index;
			l=index+1;
		}
		else if(val>v[index])
		{
			l=index+1;
		}
		else
		{
			r=index-1;
		}
	}
	return pos;
}

int BinSearchBit(vector<uint32>& v, uint32 val)
{
	uint32 step=1,i;
	uint32 n=v.size();
	for(step=1; step<n; step<<=1) ;
	for(i=0; step; step>>=1)
		if(i+step<n && v[i+step]<=val)
			i+=step;
	return i;
}

int BinSearchBitR(vector<uint32>& v, uint32 val)
{
	uint32 step=1,i;
	uint32 n=v.size();
	for(step=1; step<n; step<<=1) ;
	for(i=0; step; step>>=1)
		if(i+step<=n && v[n-i-step]>=val)
		{
			i+=step;
		}
	return n-i;
}

int main()
{
	int n,m;
	unsigned int x,op;
	fstream fin("cautbin.in", fstream::in);
	fstream fout("cautbin.out", fstream::out);
	vector<uint32> v;
	
	fin>>n;
	//cout<<n<<endl;
	for(int i=0;i <n; ++i)
	{
		fin>>x;
		v.push_back(x);
		//cout<<v[i]<<" ";
	}
	//cout<<endl;
	
	fin>>m;
	for(int i=0; i<m; ++i)
	{
		fin>>op>>x;
		switch(op)
		{
			case 0:
			{
				int rez=BinSearchBit(v,x);
				if(rez==n || v[rez]!=x)
				{
					fout<<-1<<"\n";
				}
				else
					fout<<rez+1<<"\n";
			}; break;
			
			case 1:
			{
				fout<<BinSearchBit(v,x)+1<<"\n";
			}; break;
			
			case 2:
			{
				fout<<BinSearchBitR(v,x)+1<<"\n";
			}; break;
		}
	}
	
	//cout<<BinSearchBitR(v,4)<<"\n";
	fin.close();
	fout.close();
	return 0;
}