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

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


 


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

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>>x;
 if(caz==0) g<<cazul_0(x)<<endl;
 if(caz==1) g<<cazul_1(x)<<endl; 
 if(caz==2) g<<cazul_2(x)<<endl; 
}

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