#include <bits/stdc++.h>

using namespace std;

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

const int max_n = (int)1e5 + 5;

int n, m;

int v[max_n];

int main() {
  in >> n;
  for (int i = 1; i <= n; i++) {
    in >> v[i];
  }
  in >> m;
  for (int i = 1; i <= m; i++) {
    int op, x;
    in >> op >> x;
    if (op == 0) {
      int l = 1, r = n, ans = -1;
      while (l <= r) {
        int m = (l + r) / 2;
        if (v[m] <= x) {
          ans = m;
          l = m + 1;
        } else {
          r = m - 1;
        }
      }
      if (v[ans] != x) {
        ans = -1;
      }
      out << ans << "\n";
    } else if (op == 1) {
      int l = 1, r = n, ans = -1;
      while (l <= r) {
        int m = (l + r) / 2;
        if (v[m] <= x) {
          ans = m;
          l = m + 1;
        } else {
          r = m - 1;
        }
      }
      out << ans << "\n";
    } else if (op == 2) {
      int l = 1, r = n, ans = -1;
      while (l <= r) {
        int m = (l + r) / 2;
        if (v[m] >= x) {
          ans = m;
          r = m - 1;
        } else {
          l = m + 1;
        }
      }
      out << ans << "\n";
    }
  }
  return 0;
}