//Cautare binara pe biti - LogN
#include <fstream>
#define Nmax 100099
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 = (1<<30), 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;
}
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)
        {
            //cea mai mare pozitie pe care se afla un element cu valoarea 
            //mai mica sau egala cu x in sir.
            int step=P,i;
            for(i=0; step ; step>>=1)
                if(i+step<=N && v[i+step]<=x)i+=step;
            g<<i<<'\n';
        }
        if(tip==2)
        {
            //cea mai mica pozitie pe care se afla un element cu valoarea
            //mai mare sau egala cu x in sir.
            int step=P,i;
            for(i=N; step ; step>>=1)
                if(i-step>0  && v[i-step]>=x)i-=step;
            g<<i<<'\n';
        }
    }
    f.close();g.close();
    return 0;
}