#include <fstream>

using namespace std;

int v[100001];
int main() {
  int N, M, w, 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;
    fin >> x;
    if(w == 0){
      contor = 0;
       st = 1;
       dr = N;
      while(st <= dr){
        int mij = (st + dr) / 2; 
        if(v[mij] == x){
          solutie = mij;
          st = mij + 1;
          contor++;
        }
        else if(v[mij] < x){
          st = mij + 1;
        }
        else if(v[mij] > x){
          dr = mij - 1;
        }
      }
      if(contor == 0){
        fout << -1 << "\n";
      }
      else{
        fout << solutie << "\n";
      }
    }
    else if(w == 1){
      st = 1;
      dr = N;
      while(st <= dr){
        int mij = (st + dr) / 2; 
        if(v[mij] <= x){
          st = mij + 1;
          solutie = mij;
        }
        else{
          dr = mij - 1;
        }
      }
     fout << solutie << "\n";

    }
    else if(w == 2){
      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 << "\n";
    }
  }


}