#include <bits/stdc++.h>

using namespace std;

#define GUARD(expr) \
  do {              \
    if (!(expr)) {  \
      return 1;     \
    }               \
  } while (0)

int main() {
#ifndef LOCAL
  freopen("cautbin.in", "r", stdin);
  freopen("cautbin.out", "w", stdout);
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  size_t N;
  GUARD(cin >> N && N <= 100'000);
  vector<size_t> X(N);
  for (size_t i = 0; i < N; ++i) {
    GUARD(cin >> X[i] && X[i] < (static_cast<size_t>(1) << 32));
  }
  size_t M;
  GUARD(cin >> M && M <= 100'100);
  for (; M--;) {
    size_t o;
    GUARD(cin >> o && (o == 0 || o == 1 || o == 2));
    size_t x;
    GUARD(cin >> x);
    size_t p = lower_bound(X.begin(), X.end(), x) - X.begin();
    GUARD(1 <= p);
    size_t const q = upper_bound(X.begin(), X.end(), x) - X.begin();
    GUARD(q < N - 1);
    if ((X[p] == x)) {
      cout << (o == 2 ? (p + 1) : q);
    } else {
      cout << (o == 0 ? -1 : (o == 1 ? p : q));
    }
    cout << '\n';
  }
  return 0;
}