#include  <iostream>
#include  <fstream>

using namespace std;

ifstream in("cautbin.in");
ofstream out("cautbin.out");

const int Nmax = 1e5 + 5;
int V[Nmax], n;

int CB0(int st, int dr,int x)
{
  int poz = -1;
  while(st <= dr)
  {
    int m = (st + dr) / 2;//st + (dr - st) / 2;
    if(V[m] == x)
      poz = m, st = m + 1;
    else
      if(V[m] < x)
        st = m + 1;
      else
        dr = m - 1;
  }
  return poz;
}

int CB1(int st, int dr, int x)
{
  int poz;
  while(st <= dr)
  {
    int m = (st + dr) / 2;
    if(V[m] <= x) //cea mai mare poz pe care se afla un el <= x
      poz = m, st = m + 1;
    else
      dr = m - 1;
  }
  return poz;
}

int CB2(int st, int dr, int x)
{
  int poz;
  while(st <= dr)
  {
    int m = (st + dr) / 2;
    if(V[m] >= x)
      poz = m, dr = m - 1;
    else
      st = m + 1;
  }
  return poz;
}

int main()
{
  in>>n;
  for(int i = 1; i <= n; i++)
    in>>V[i];
  int q;
  for(in>>q; q; q--)
  {
    int cer, nr;
    in>>cer>>nr;
    if(!cer)
      out<<CB0(1, n, nr)<<'\n';
    else if(cer == 1)
      out<<CB1(1, n, nr)<<'\n';
    else
      out<<CB2(1, n, nr)<<'\n';
    //cout<<cer<<' '<<nr<<endl;
  }
}