#include<fstream>
using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
   int v[1000001] ;
int Cautare(int v[] , int n , int x  ){
     long long  st = 1  , dr = n , pzmax = -1  ; 
          while(st<=dr){
             long long mij = (st+dr)/2;
                  if(v[mij]==x){
                       if(pzmax<mij)
                          pzmax = mij;
                            st = mij + 1 ; 
                  }else if(v[mij] < x ){
                       st  = mij + 1 ; 
                  }else {
                     dr = mij - 1 ; 
                  }
          }
          return pzmax;
}
int LowerBounds(int v[] , int n , int x ){
        int st = 1  , dr = n ; 
          while(st<=dr){
                int mij = (st+dr)/2;
                  if(v[mij]==x){
                       return mij ; 
                  }else if(v[mij] > x ){
                       dr = mij - 1 ; 
                  }else {
                     st = mij + 1  ; 
                  }
          }
          return dr ; 
}
int UpperBounds(int v[] , int n , int  x ){
    int st = 1  , dr = n ; 
          while(st<=dr){
                int mij = (st+dr)/2;
                  if(v[mij]==x){
                       return mij ; 
                  }else if(v[mij] > x ){
                       dr = mij - 1 ; 
                  }else {
                     st = mij + 1  ; 
                  }
          }
          return st ; 
}
int main(){
     
int n , k , x , q  ;
     cin>>n;
       for(int i = 1 ; i <= n ; i ++ )
         cin>>v[i];
 
      cin>>k;
        for(int i = 1 ; i <= k ; i ++ ){
              cin>>q>>x;
               if(q==0)
                  cout<<Cautare(v,n,x)<<endl;
                 if(q==1)
                    cout<<LowerBounds(v,n,x)<<endl;
                   if(q==2)
                  cout<<UpperBounds(v,n,x)<<endl;
        }
 
 
 
 
 
 
    return 0 ; 
}