#include<fstream>
#define max 100008
using namespace std;
int x,y,n,m,v[max];

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int caz_0(int x)
{int m,l,r;
l=1;
r=n;
while (l!=r)
{m=(l+r)/2;
if(x>=v[m])
l=m;
else
r=m-1;}
if(x!=v[l])
return -1;
return l;
}
 
int caz_1(int x)
{int m,l,r;
l=1;
r=n;
while (l!=r)
{m=(l+r)/2;
if(x<=v[m])
r=m;
else
l=m+1;}
if(v[l]>=x)
return l-1;
return l;
}
 

int caz_2(int x)
{int m,l,r;
l=1;
r=n;
while (l!=r)
{m=(l+r)/2;
if(x>=v[m])
l=m;
else
r=m-1;}
if(v[l]<x)
return l+1;
return l;
} 

int main ()
{f>>n;
for(int i=1;i<=n;i++)
f>>v[i];
f>>m;
for(int i=1;i<=m;i++)
{f>>x>>y;
if(x==0)
g<<caz_0(y)<<"\n";
if(x==1)
g<<caz_1(y)<<"\n";
if(x==2)
g<<caz_2(y)<<"\n";}
f.close ();
g.close ();
return 0;
}