#include<iostream>
#include<fstream>

using namespace std;

int a[100005];
int caut0x(int st ,int dr,int x)
{long mij;
while(st<=dr){
	mij=(st+dr)/2;
	if(a[mij]<=x)
		st=mij+1;
		else dr=mij-1;
    }
    mij=(dr+st)/2;
 
    if (a[mij]>x)mij--;
    if (a[mij]==x)
	return mij;
return -1;
}
int caut1x(int st,int dr,int x)
{long mij;
while(st<x){
	mij=(x+st)/2;
	if(a[mij]<=x)
		st=mij+1;
	else dr=mij-1;
    }
    mij=(x+st)/2;
 
    if (a[mij]>x);
	return mij+1;}
int caut2x(int st,int dr,int x)
{long mij;
while(x<=dr){
	mij=(dr+x)/2;
	if(a[mij]<=x)
		dr=mij-1;
	else x=mij+1;
    }
    mij=(dr+x)/2;
 
    if (a[mij]<x)mij++;
	return mij;}
int main()
{
long n,i,m,x1,st1,dr1,y;
	ifstream f("cautbin.in");
	ofstream g("cautbin.out");
f>>n;
for(i=1;i<=n;i++)f>>a[i];
st1=1;dr1=n;
f>>m;
for(i=1;i<=m;i++){
	f>>y>>x1;
if(y==0)g<<caut0x(st1,dr1,x1)<<endl;
if(y==1)g<<caut1x(st1,dr1,x1)<<endl;
if(y==2)g<<caut2x(st1,dr1,x1)<<endl;}
}