#include <fstream>
using namespace std;

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

 int n;
 int mid, v[100000];

int caut( int st, int dr, int x){
    int save=-1;
while ( st<= dr ) {
  int mid= ( st + dr ) /2;
  if ( x>=v[mid] ) st=mid+1; else dr=mid-1;
  if ( x==v[mid]  ) save=mid  ;
}
 return save;
}
int caut1( int st, int dr, int x){
    int save;
while ( st<= dr ) {
  int mid= ( st + dr ) /2;
  if ( x>=v[mid] ) st=mid+1; else dr=mid-1;
  if ( x>=v[mid]  ) save=mid  ;
}
 return save;
}
int caut2( int st, int dr, int x){
    int save;
while ( st<= dr ) {
  int mid= ( st + dr ) /2;
  if ( x>v[mid] ) st=mid+1; else dr=mid-1;
  if ( x<=v[mid]  ) save=mid  ;
}
 return save;
}



int main()
{
    in>>n;
    for(int i=1; i<=n; i++)
        in>>v[i];
   int nr; in>>nr;
   int x;

 for(int i=1; i<=nr; i++){
        int a; in>>a>>x;
        if ( a==0 ) out<<caut(1,n,x)<<'\n';
        if ( a==1) out << caut1(1,n,x)<<'\n';
        if ( a==2 ) out<<caut2(1,n,x)<<'\n';
       }

    return 0;
}