#include <iostream>
#include <fstream>
using namespace std;

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

int v[100005];

int cautare_binara0(int nr, int n)
{
      int st = 1, dr = n, mij, rez = -1;
      bool ok = false;
      while (st <= dr)
      {
            mij = (st + dr) / 2;
            if (v[mij] == nr)
            {
                  rez = mij;
                  ok = true;
                  st = mij + 1;
            }
            if (v[mij] > nr)
                  dr = mij - 1;
            else
                  st = mij + 1;
      }

      if (ok == true)
            return rez;
      else
            return -1;
}


int cautare_binara1(int nr, int n)
{
      int st = 1, dr = n, mij, rez = -1;
      bool ok = false;
      while (st <= dr)
      {
            mij = (st + dr) / 2;
            if (v[mij] <= nr)
            {
                  rez = mij;
                  ok = true;
                  st = mij + 1;
            }
            if (v[mij] > nr)
                  dr = mij - 1;
      }

      if (ok == true)
            return rez;
      else
            return -1;
}


int cautare_binara2(int nr, int n)
{
      int st = 1, dr = n, mij, rez = -1;
      bool ok = false;
      while (st <= dr)
      {
            mij = (st + dr) / 2;
            if (v[mij] >= nr)
            {
                  rez = mij;
                  ok = true;
                  dr = mij - 1;
            }
            if (v[mij] < nr)
                  st = mij + 1;
      }

      if (ok == true)
            return rez;
      else
            return -1;
}

int main()
{
      int n, m, nr_test, nr_c;
      fin >> n;
      for(int i = 1; i <= n; ++i)   
            fin >> v[i];
      fin >> m;
      for(int i = 1; i <= m; ++i)
      {
            fin >> nr_test >> nr_c;
            if(nr_test == 0)
                  fout << cautare_binara0(nr_c, n) << '\n';
            if(nr_test == 1)
                  fout << cautare_binara1(nr_c, n) << '\n';
            if(nr_test == 2)
                  fout << cautare_binara2(nr_c, n) << '\n';
      }
      return 0;
}