#include <stdio.h>
#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i,a,b) for(int i = a; i < b; i++)

using namespace std;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int Nmax = 100555;

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


int N, M, q, x, a[Nmax];

int main(void) {
  fin >> N;
  rep(i, N) { fin >> a[i]; }

  fin >> M;
  while(M--) {
    fin >> q >> x;
    int pos = -2;

    if (q == 0) {
      pos = upper_bound(a, a + N, x) - a;
      --pos;
      if (pos < 0 || a[pos] < x) {
        pos = -2;
      }
    } else if (q == 1) {
      pos = upper_bound(a, a + N, x) - a;
      --pos;
    } else if (q == 2) {
      pos = lower_bound(a, a + N, x) - a;
    } else {
      continue;
    }
    fout << pos + 1 << '\n';
  }

  return 0;
}