#include<fstream>
using namespace std;
int v[100020];

int cazul_0(int val,int st,int dr)
{  int mid;
while(st<=dr)
   {mid=(st+dr)/2;
   if(v[mid]<=val) st=mid+1;
   else dr=mid-1;}
mid=(st+dr)/2;
if(v[mid]>val) mid--;
if(v[mid]==val) return mid;
 else return -1;}
  
int cazul_1(int val, int st, int dr)
{ int mid;
while(st<dr)
  { mid=(st+dr)/2;
    if(v[mid]<=val)  st=mid+1;        
    else dr=mid;}
mid=(st+dr)/2;
if(v[mid]>val) --mid;
return mid;}
   
int cazul_2(int val, int st, int dr)
{ int mid;
while(st<dr)
  {mid=(st+dr)/2;
   if(v[mid]<val) st=mid+1;
   else dr=mid; }
mid=(st+dr)/2;
if(v[mid]<val) ++mid;
return mid; }

int main() 
{ int N, M, caz, x;
ifstream f("cautbin.in");
ofstream g("cautbin.out");

f>>N;
for(int i=1;i<=N;i++)
f>>v[i];

f>>M;
for(int i=0;i<M;i++){
 f>>caz>>x;
 if(caz==0) g<<cazul_0(x,1,N)<<"\n";
 if(caz==1) g<<cazul_1(x,1,N)<<"\n"; 
 if(caz==2) g<<cazul_2(x,1,N)<<"\n"; 
}
f.close();
g.close();
return 0;
}