#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
ifstream fin ("cautbin.in");
ofstream fout("cautbin.out");
long long v[500010];
int i,n,m,x,c;
int cautbin1(long long v[100010],int n,int x)
{
	int mid,l,r;
	l=1;
	r=n;
	while(l!=r)
	{
		mid=(l+r+1)/2;
		// cerr<<mid<<"l"<<l<<"r"<<r<<endl;
		// cerr << v[mid] << ' ' << x << endl;
		if(v[mid]<=x)
			l=mid;
		else r=mid-1;
	}
	return l;
}
int cautbin2(long long v[100010],int n,int x)
{
	int mid,l,r;
	l=1;
	r=n;
	while(l!=r)
	{
		mid=(l+r)/2;
		if(v[mid]>=x)
			r=mid;
		else l=mid+1;
	}
	return l;
}

int main()
{
	fin>>n;
	for(i=1;i<=n;i++)
	{
		fin>>v[i];
	}
	fin>>m;
	long long  nr;
	for(i=1;i<=m;i++)
	{
		fin>>c;
		fin>>x;
		if(c==0)
		{
			nr=cautbin1(v,n,x);
			if(v[nr]==x)
				fout<<nr<<'\n';
			else fout<<-1<<'\n';
		}
		if(c==1)
			fout<<cautbin1(v,n,x)<<'\n';
		if(c==2)
			fout<<cautbin2(v,n,x)<<'\n';
	}
	return 0;
}