#include <fstream>
 
using namespace std;
int v[100001], w[100001];

int main() {
  int N, M,  x, solutie, st, dr;
  ifstream fin("cautbin.in");
  ofstream fout("cautbin.out");
  fin >> N;
  int contor = 0;
  for(int i = 1; i <= N; i++){
    fin >> v[i];
  }
  fin >> M;
  for(int j = 1; j <= M; j++){
    fin >> w[j];
    fin >> x;
    if(w[j] == 0){
       st = 1;
       dr = N;
      while(st <= dr){
        int mij = (st + dr) / 2; 
        if(v[mij] == x){
          solutie = mij;
          dr = mij - 1;
          contor++;
        }
        else if(v[mij] < x){
          st = mij + 1;
        }
        else if(v[mij] > x){
          dr = mij - 1;
        }
      }
      if(contor == 0){
        fout << -1;
      }
      else{
        fout << solutie;
      }
    }
    else if(w[j] == 1){
      st = 1;
      dr = N;
      while(st <= dr){
        int mij = (st + dr) / 2; 
        if(v[mij] <= x){
          solutie = mij;
          dr = mij - 1;
        }
        else{
          st = mij + 1;
        }
        fout << solutie;
      }
 
    }
    else if(w[j] == 2){
      st = 1;
      dr = N;
      while(st <= dr){
        int mij = (st + dr) / 2;
        if(v[mij] >= x){
          solutie = mij;
          st = mij + 1;
        }
        else{
          dr = mij - 1;
        }
        fout << solutie;
      }
    }

    fout << '\n';
 
  }
 
 
}