#include<fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int i,n,a[100020],mij=0,x,y,z;
void citire()
{f>>n;
for(i=1;i<=n;i++)  
f>>a[i];}
int sch1(int l,int r,int s)
{while(l<=r)
{mij=l+(r-l)/2;
if(a[mij]<=s)
l=mij+1;
else
r=mij-1;}
mij=l+(r-l)/2;
if(a[mij]>s)
mij--;
if(a[mij]==s)
return mij;
return -1;}
int sch2(int l,int r,int s)
{while(l<r)
{mij=l+(r-l)/2;
if(a[mij]<=s)
l=mij+1;
else
r=mij;}
mij=l+(r-l)/2;
if(a[mij]>s)
--mij;
return mij;}
int sch3(int l,int r,int s)
{while(l<r)
{mij=l+(r-l)/2;
if(a[mij]<s)
l=mij+1;
else
r=mij;}
mij=l+(r-l)/2;
if(a[mij]<s)
++mij;
return mij;}
int main()
{citire();
f>>x;
for(i=0;i<x;i++)
{f>>y>>z;
 if(y==0)
 g<<sch1(1,n,z)<<endl;
 else
 if(y==1)
 g<<sch2(1,n,z)<<endl;
 else
 if(y==2)
 g<<sch3(1,n,z)<<endl;}
f.close();
g.close();
return 0;}