#include <fstream>
#include <vector>

using namespace std;

int cautbin0(vector<int> &v, int x)
{
  int left, right, middle;

  left = 0;
  right = v.size();

  while (right - left > 1)
  {
    middle = left + (right - left) / 2;

    if (v[middle] <= x)
    {
      left = middle;
    }
    else
    {
      right = middle;
    }
  }
  if (v[left] == x)
  {
    return left + 1;
  }
  return -1;
}

int cautbin1(vector<int> &v, int x)
{
  int left, right, middle;

  left = 0;
  right = v.size();

  while (right - left > 1)
  {
    middle = left + (right - left) / 2;

    if (v[middle] <= x)
    {
      left = middle;
    }
    else
    {
      right = middle;
    }
  }
  return left + 1;
}

int cautbin2(vector<int> &v, int x)
{
  int left, right, middle;

  left = 0;
  right = v.size();

  while (right - left > 1)
  {
    middle = left + (right - left) / 2;

    if (v[middle] >= x)
    {
      right = middle;
    }
    else
    {
      left = middle;
    }
  }
  return right + 1;
}

int main()
{
  ifstream in;
  ofstream out;

  in.open("cautbin.in");
  out.open("cautbin.out");

  int n;
  in >> n;
  vector<int> v(n);

  for (int i = 0; i < n; ++i)
    in >> v[i];

  int q;
  in >> q;

  int type, x;
  for (int i = 0; i < q; ++i)
  {
    in >> type >> x;

    switch (type)
    {
    case 0:
      out << cautbin0(v, x) << '\n';
      break;
    case 1:
      out << cautbin1(v, x) << '\n';
      break;
    case 2:
      out << cautbin2(v, x) << '\n';
      break;
    }
  }

  in.close();
  out.close();
}