#include<fstream>
#include<iostream>
using namespace std;
int v[100001], N;

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

int cazul_2(int val)
{  int poz, st=1, dr=N;
while(st<dr)
{poz=(st+dr)/2;
if(v[poz]<val)
st=poz+1;
else dr=poz; }
poz=st;
if(v[poz]<val)
poz++;
return poz; }


int main() 
{ int M, caz, x, rez;

fstream f("cautbin.in", ios::in);
fstream g("cautbin.out", ios::out);

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

f>>M;
for(int i=1;i<=M;i++)
{f>>caz; 
 f>>x;
 if(caz==0){ rez=cazul_0(x); g<<rez<<endl; }
 if(caz==1){ rez=cazul_1(x); g<<rez<<endl; }
 if(caz==2){ rez=cazul_2(x); g<<rez<<endl; }
}

f.close();
g.close();
return 1;
}