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

ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int n, a[100001], m, q, xq;

int cb0(int x)
{
  int st = 1, dr = n, rez = -1;
  while(st <= dr)
  {
    int mid = (st + dr) / 2;
    if(a[mid] <= x)
    {
      if(a[mid] == x) rez = mid;
      st = mid + 1;
    }
    else dr = mid - 1;
  }
  return rez;
}

int cb1(int x)
{
  int st = 1, dr = n, rez = -1;
  while(st <= dr)
  {
    int mid = (st + dr) / 2;
    if(a[mid] <= x)
    {
      rez = mid;
      st = mid + 1;
    }
    else
    {
      dr = mid - 1;
    }
  }
  return rez;
}

int cb2(int x)
{
  int st = 1, dr = n, rez = - 1;
  while(st <= dr)
  {
    int mid = (st + dr) / 2;
    if(a[mid] >= x)
    {
      rez = mid;
      dr = mid - 1;
    }
    else
    {
      st = mid + 1;
    }
  }
  return rez;
}

int main()
{
  cin >> n;
  for(int i = 1; i <= n; i++)
  {
    cin >> a[i];
  }

  cin >> m;
  while(m--)
  {
    cin >> q >> xq;
    if(q == 0) cout << cb0(xq) << '\n';
    else if(q == 1) cout << cb1(xq) << '\n';
    else if(q == 2) cout << cb2(xq) << '\n';
  }
}