#include<fstream>
using namespace std;
int n,a[100001],m,x,y,i;
int bs0(int st, int dr, int x)
{
int mij;
while(st<=dr)
{
mij=(st+dr)/2;
if(a[mij]<=x)
st=mij+1;
else
dr=mij-1;
}
mij=(st+dr)/2;
if(a[mij]>x)
--mij;
if(a[mij]==x)
return mij;
else
return -1;
}
int bs1(int st, int dr, int x)
{
int mij;
while(st<dr)
{
mij=(st+dr)/2;
if(a[mij]<=x)
st=mij+1;
else
dr=mij;
}
mij=(st+dr)/2;
if(a[mij]>x)
--mij;
 
return mij;
}
int bs2(int st, int dr, int x)
{
int mij;
while(st<dr)
{
mij=(st+dr)/2;
if(a[mij]>=x)
dr=mij;
else
st=mij+1;
}
mij=(st+dr)/2;
if(a[mij]<x)
++mij;
 
return mij;
}
int main()
{
ifstream f("cautbin.in");
ofstream g("cautbin.out");
f>>n;
for(i=1;i<=n;i++)
f>>a[i];
f>>m;
for(i=1;i<=m;i++)
{
f>>y>>x;
if(y==0)
g<<bs0(1,n,x)<<"\n";
else
if(y==1)
g<<bs1(1,n,x)<<"\n";
else
if(y==2)
g<<bs2(1,n,x)<<"\n;
}
return 0;
}