#include <fstream.h>
#define NMAX 100001

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int Z,N,M;
long A[NMAX];




int cautbin(int s, int d, int x)
{int m;
if (s>d)  if(Z==0) return -1; else return d;
  else {m=s+(d-s)/2;
       if(A[m]==x) return m;
        else if(x<A[m]) return cautbin(s,m-1,x);
               else return cautbin(m+1,d,x);
        }
}  

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=-1; if(N>20) p=p-1;  
          while(A[p+1]<=x ) p=p+1;}
 if(Z==2) {p=p+1; if(N>20) p=p+1;
          while(A[p-1]>=x) p=p-1;}
 if(p>N) p=N;
 fout<<p<<"\n";
 }
}



int main()
{citire();



fin.close();
fout.close();
return 0;
}