#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 ((s+(d-s))/2-1);
  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 (p<0) p=p+1; 
if(Z==0 && p!=-1) {while(A[p+1]==x) p=p+1;} 
if(Z==1) {while(A[p+1]<=x && p<N) p=p+1;}
if(Z==2) {while (A[p]<x) p=p+1;}
 fout<<p<<"\n";
 }
}
 
 
 
int main()
{citire();
 
 
 
fin.close();
fout.close();
return 0;
}