#include<fstream>
using namespace std;

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

int v[100001];

int main()
{
  int n, m, i, q, x, ok, st, dr, mij, p;
  fin>> n;
  for(i = 1; i <= n; i++) fin>> v[i];
  fin>> m;
  for(i = 1; i <= m; i++)
    {
      fin>> q>> x;
      st = 1, dr = n, ok = true;
      p = -1;
      if(q == 0)
      {
        while(st <= dr && ok)
          {
            mij = (st+dr)/2;
            if(v[mij] == x && (mij == n || v[mij+1] > v[mij]))
            {
              p = mij;
              ok = true;
            }
            else if(v[mij] <= x) st = mij+1;
            else dr = mij-1;
          }
        fout<< p<< endl;
      }
      if(q == 1)
      {
        while(st <= dr && ok)
          {
            mij = (st+dr)/2;
            if(v[mij] <= x && (mij == n || v[mij+1] > v[mij]))
            {
              p = mij;
              ok = true;
            }
            else if(v[mij] <= x) st = mij+1;
            else dr = mij-1;
          }
        fout<< p<< endl;
      }
      if(q == 2)
      {
        while(st <= dr && ok)
          {
            mij = (st+dr)/2;
            if(v[mij] >= x && (mij == 1 || v[mij-1] < v[mij]))
            {
              p = mij;
              ok = true;
            }
            else if(v[mij] <= x) st = mij+1;
            else if(v[mij] >= x) dr = mij-1;
          }
        fout<< p<< endl;
      }
    }
  fout.close();
  return 0;
}