#include <iostream>
#include <fstream>

using namespace std;
ifstream in ("cautbin.in");
ofstream out ("cautbin.out");
unsigned int v[100001];
int main()
{
  unsigned int n ,m ,a ,b ,st = 0,dr = 0 ,mid = 0 ,i;
  in>>n;
  for(i = 1 ; i <= n ;i++){
    in>>v[i];
  }
  v[n+1] = 3000000000;
  //cout<<v[n+1];
  in>>m;
  for(i = 0 ; i < m ;i++){
    in>>a>>b;
    st = 1;
    dr = n;
    mid = (st + dr)/2;
    if(a == 0){
      while(true){
        if(v[mid] == b && v[mid + 1] != mid){
          out<<mid<<'\n';
          break;
        }
        if(v[mid]<=b){
          st = mid + 1;
        }
        if(b < v[mid]){
          dr = mid - 1;
        }
        if(v[mid] < b && b < v[mid + 1]){
          out<<"-1"<<'\n';
          break;
        }
        mid = (st + dr)/2;
     }
    } else if (a == 1){
       while(true){
        if(v[mid] <= b && b < v[mid + 1] ){
          out<<mid<<'\n';
          break;
        }
        if(v[mid]<=b){
          st = mid + 1;
        }
        if(b < v[mid]){
          dr = mid - 1;
        }
        mid = (st + dr)/2;
        //cout<<mid<<" ";
      }
    } else if (a == 2){
       while(true){
        if(v[mid] <= b && b < v[mid + 1] ){
          out<<mid + 1<<'\n';
          break;
        }
        if(v[mid]<=b){
          st = mid + 1;
        }
        if(b < v[mid]){
          dr = mid - 1;
        }
        mid = (st + dr)/2;
      }
    }
    //cout<<'\n';
  }
  return 0;
}