#include<cstdio>
#include<vector>
using namespace std;

int n,m;

vector <int> v;

void cit()
{
	int x;
	scanf("%d",&n);
	for( int i=0 ; i<n ; ++i )
	{
		scanf("%d",&x);
		v.push_back(x);
	}
}

int bs(int x)
{
	int st=0,dr=n-1,mij;
	while(st!=dr)
	{
		mij=(st+dr)/2;
		if( x < v[mij])
			dr=mij-1;
		else if( x> v[mij])
			st=mij+1;
		else
			return mij+1;
	}
	if(v[st]!=x)
		return -1;
	else
		return st+1;
}

int as(int x)
{
	int st=0,dr=n-1,mij;
	while(st!=dr)
	{
		mij=(st+dr)/2;
		if( x < v[mij])
			dr=mij-1;
		else if( x> v[mij])
			st=mij+1;
		else
			return mij+1;
	}
	while( v[st]<=x)
		++st;
	return st+1;
}

int cs(int x)
{
	int st=0,dr=n-1,mij;
	while(st!=dr)
	{
		mij=(st+dr)/2;
		if( x < v[mij])
			dr=mij-1;
		else if( x> v[mij])
			st=mij+1;
		else
			return mij+1;
	}
	while(v[st]<=x)
		++st;
	++st;
	return st+1;
}
void sol()
{
	scanf("%d",&m);
	int t,x;
	while(m--)
	{
		scanf("%d%d",&t,&x);
		if(t==0)
			printf("%d\n",bs(x));
		else if(t==1)
			printf("%d\n",as(x));
		else
			printf("%d\n",cs(x));
	}
}

int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	cit();
	sol();
	return 0;
}