//Cautare binara pe biti - LogN
#include <fstream>
#define Nmax 100099
#define MAXSTEP (1<<17)
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");

int N, M, P, v[Nmax];


//cea mai mare pozitie pe care se afla un element cu valoarea x
  //sau -1 daca aceasta valoare nu se gaseste in sir

int cb(const int v[Nmax],const int& N, const int& x) {
  int step = MAXSTEP, i;
  
  for(i = 0; step ; step >>= 1)
    if(i+step <= N && v[i+step] <= x){
      i += step;
    }

  if(v[i]==x)return i;
  return -1;
}

//cea mai mare pozitie pe care se afla un element cu valoarea 
//mai mica sau egala cu x in sir.
int cb_up(const int v[Nmax],const int& N, const int& x) {
  int step = MAXSTEP, i;
  
  for(i = 0; step ; step >>= 1)
    if(i+step <= N && v[i+step] <= x) {
      i += step;
    }
  if (i && v[i] <= x) return i;
  return -1;
}

//cea mai mica pozitie pe care se afla un element cu valoarea
//mai mare sau egala cu x in sir.
int cb_down(const int v[Nmax],const int& N, const int& x) {
  int step = MAXSTEP, i;

  for(i = N; step ; step >>= 1)
    if(i-step > 0  && v[i-step] >= x) {
      i -= step;
    }
  if (i && v[i] >= x) return i;
  return -1;
}

int main() {
  f>>N;
  for(int i = 1; i <= N; ++i) f >> v[i];
  f >> M;

  for(int i = 1; i <= M; ++i) {
      int tip, x;
      f >> tip >> x;
      
      if(!tip) {
        g << cb(v, N, x)<<'\n';
        continue;
      }

      if(tip == 1) {
        g << cb_up(v, N, x)<<'\n';
        continue;
      }

      if(tip == 2) {
        g << cb_down(v, N, x)<<'\n';
        //continue;
      }
  }
  f.close();g.close();
  return 0;
}