#include<fstream.h>
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int x,N,M,i=1,a[100001];
inline int c0(int x)
{int s=1,d=N;
 while(s<=d)
 {int m=(s+d)/2;
  if(x==a[m])
  {while(a[m]==x) m++;
   return m-1;}
  else if(x<a[m]) d=m-1;
       else       s=m+1;}
 return -1;
}
inline int c1(int x)
{int s=1,d=N,i=0;
 while(s<=d)
 {int m=(s+d)/2;
  if(x<a[m]) d=m-1;
  else {i=m; s=m+1;}}
 return i;
}
inline int c2(int x)
{int s=1,d=N,i=N+1;
 while(s<=d)
 {int m=(s+d)/2;
  if(x<=a[m]){d=m-1;i=m;}
       else   s=m+1;}
 return i;
}
int main()
{f>>N;
for(;i<=N;++i) f>>a[i];
f>>M;
for(;M;--M)
{short r;
 f>>r>>x;
 switch(r)
 {case 0 :g<<c0(x)<<'\n';break;
  case 1 :g<<c1(x)<<'\n';break;
  default:g<<c2(x)<<'\n';
 }
}
 return 0;
}