#include <fstream>

using namespace std;

int main() {
  int N, v[100000], M, w[100000], 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;
      }
    }

  }


}