#include<fstream>
#include<algorithm>
using namespace std;

int n;
int v[100001];

ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int upperBound(int a){
   int l=1 , r=n;
   int poz=0;
 //  cout<<"a="<<a<<endl;
   while ( l<=r){
      int mid=(l+r)/2;
    // cout<<"mid="<<mid<<endl;
     if( v[mid]>= a ){
         //  cout<<"v[mid]="<<v[mid]<<endl;
          if ( v[mid]==a) {
                poz=mid;
//cout<<"poz="<<poz<<endl;
               //  break;
          }
          r=mid-1;
        //  cout<<"poz1="<<poz<<endl;
     }
      else {
       l=mid+1;
     }
        // cout<<" l= "<<l<<" r= " <<r<<" mid = "<<mid<< "  v[mid]= "<< v[mid]<<endl;
   }
  // cout<<"poz final="<<poz<<endl;
   if ( poz==0 ) poz=r;
   return poz;
}

int lowerBound(int a){
   int l=1 , r=n;
   int poz=0;
   //cout<<"a="<<a<<endl;
   while ( l<r){
      int mid=(l+r)/2;
   //cout<<"mid="<<mid<<endl;
     if( v[mid]>= a ){
          //  cout<<"v[mid]="<<v[mid]<<endl;
          if ( v[mid]==a) {
                poz = mid;
                //cout<<"poz1="<<poz<<endl;
                break;
          }
          r=mid-1;
         // cout<<"poz1="<<poz<<endl;
     }
      else {
       l=mid+1;
      }
       //cout<<" l= "<<l<<" r= " <<r<<" mid = "<<mid<< "  v[mid]= "<< v[mid]<<endl;
   }

  // cout<<"poz final="<<poz<<endl;
   if ( poz==0 ) poz=l;
   return poz;
}


int catbin( int a){
     int l=1 , r=n;
    int poz=0;
  //   cout<<"a="<<a<<endl;
     while ( l<=r){
        int mid=(l+r)/2;
      // cout<<"mid="<<mid<<endl;
        if(v[mid] == a) {
         //   cout<<"v[mid]="<<v[mid]<<endl;
            poz = mid;
        //    cout<<"poz1="<<poz<<endl;
            break;
         }
         else if(v[mid] < a) {
            l = mid + 1;
         }
         else {
            r = mid - 1;
        }

       // cout<<" l= "<<l<<" r= " <<r<<" mid = "<<mid<< "  v[mid]= "<< v[mid]<<endl;
    }
   // cout<<"poz final="<<poz<<endl;
      if ( poz==0 ) poz=-1;
   return poz;
}



int main()
{
    int m,x,y;
    cin>>n;
    for ( int i=1;i<=n;i++){
        cin>>v[i];
    }
    cin>>m;
    for ( int j=1;j<=m;j++){
       cin>>x>>y;
       int f=0;
      // cout<<"x="<<x<<endl;
      // cout<<f<<endl;
      if ( x==0 ){
          f= catbin(y);

      }
      if ( x==1){
        f=upperBound  (y);
      }
      else if ( x==2){
         f =lowerBound(y );
      }
       cout<<f<<endl;
    }
}