#include <fstream>
#define nmax 100000
using namespace std;
 ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int v[nmax],n;
int cb0(int st, int dr, int x)
{
int piv;
while(st<=dr)
{
piv=(st+dr)/2;
if(v[piv]<=x) st=piv+1;
else dr=piv-1;
}
piv=(st+dr)/2;
if(v[piv]>x) piv--;
if(v[piv]==x) return piv;
return -1;
}
int cb1(int st, int dr, int x)
{
int piv;
while(st<dr)
{
piv=(st+dr)/2;
if(v[piv]<=x) st=piv+1;
else dr=piv;
}
piv=(st+dr)/2;
if(v[piv]>x) piv--;
 return piv;
}
int cb2(int st, int dr, int x)
{
int piv;
while(st<dr)
{
piv=(st+dr)/2;
if(v[piv]<x) st=piv+1;
else dr=piv;
}
piv=(st+dr)/2;
if(v[piv]<x)
piv++;
return piv;
}
int main()
{
int st,dr,i,x,m,c;
cin>>n;
for(i=1; i<=n; i++)
cin>>v[i];
cin>>m;
st=1; dr=n;
for(i=1; i<=m; i++)
{
cin>>c>>x;
if(c==0)
cout<<cb0(1,n,x)<<'\n';
if(c==1) 
cout<<cb1(1,n,x)<<'\n';
if(c==2)
cout<<cb2(st,dr,x)<<'\n';
}
return 0;
}