//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], tip, x;


//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(P=1; P<=N; P<<=1);
    for(int k=1; k<=M; ++k)
    {
        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;
}