#include <stdio.h>

using namespace std;

int n, a[100001], m, c, v;

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

int rez1 (int x) {
  int st = 1, dr = n, mij;
  int r = 0;
  while (st <= dr) {
    mij = st + (dr - st) / 2;
    if (a[mij] <= x) {
      r = mij;
      st = mij + 1;
    }
    else
      dr = mij - 1;
  }
  return r;
}

int rez2 (int x) {
  int st = 1, dr = n, mij;
  int r = 0;
  while (st <= dr) {
    mij = st + (dr - st) / 2;
    if (a[mij] < x)
      st = mij + 1;
    else {
      r = mij;
      dr = mij - 1;
    }
  }
  return r;
}

int main()
{
  freopen("cautbin.in","r",stdin);
  freopen("cautbin.out","w",stdout);
  scanf ("%d", &n);
  for (int i = 1; i <= n; i++)
    scanf ("%d", &a[i]);
  scanf ("%d", &m);
  for (int i = 1; i <= m; i++) {
    scanf ("%d%d", &c, &v);
    if (c == 0)
      printf ("%d\n", rez0 (v));
    else
      if (c == 1)
        printf ("%d\n", rez1 (v));
      else
        printf ("%d\n", rez2 (v));

  }
  return 0;
}