#include <fstream.h>
02.#define NMAX 100001
03. 
04.ifstream fin("cautbin.in");
05.ofstream fout("cautbin.out");
06. 
07.int Z,N,M;
08.long A[NMAX];
09. 
10. 
11. 
12. 
13.int cautbin(int s, int d, int x)
14.{int m;
15.if (s>d)  if(Z==0) return -1; else return d;
16.  else {m=s+(d-s)/2;
17.       if(A[m]==x) return m;
18.        else if(x<A[m]) return cautbin(s,m-1,x);
19.               else return cautbin(m+1,d,x);
20.        }
21.} 
 
void citire()
{int i,x,p;
fin>>N;
for(i=1;i<=N;i++)
fin>>A[i];
fin>>M;
for(i=1;i<=M;i++)
{fin>>Z>>x;
p=cautbin(1,N,x);
  
 if(Z==0 && p!=-1) {while(A[p+1]==x) p=p+1;}
 if(Z==1) {p=p-1; if(N>20) p=p-2;
          while(A[p+1]<=x) p=p+1;}
 if(Z==2) {p=p+1; if(N>20) p=p+2;
          while(A[p-1]>=x) p=p-1;}
 fout<<p<<"\n";
 }
}
 
 
 
int main()
{citire();
 
 
 
49.fin.close();
50.fout.close();
51.return 0;
}