#include <fstream>
using namespace std;

ifstream cin("cautbin.in");
ofstream cout("cautbin.out");

int n, m, q, x, i;
int a[100001];

int caut(int x)
{
	int index = 0;
	for(int bit = 16; bit >= 0; bit--)
	{
		index += (1<<bit);
		if(index > n || a[index] > x)
			index -= (1<<bit);
	}

	if(a[index] == x)
		return index;
	return -1;
}

int uprb(int x)
{
	int index = 0;
	for(int bit = 16; bit >= 0; bit--)
	{
		index += (1<<bit);
		if(index > n || a[index] > x)
			index -= (1<<bit);
	}

	return index;
}

int lwrb(int x)
{ 
	int index = 0;
	for(int bit = 16; bit >= 0; bit--)
	{
		index += (1<<bit);
		if(index > n || a[index] >= x)
			index -= (1<<bit);
	}

	return index+1;

}



int main()
{
	cin>>n;
    for(i=1;i<=n;++i)
        cin>>a[i];
    cin>>m;
    for(i=0;i<m;++i)
    {
        cin>>q>>x;
        if(q==1) cout<<uprb(x)<<'\n';
        else if(q==2) cout<<lwrb(x)<<'\n';
        else cout<<caut(x)<<'\n';
    }
	return 0;
}