#include <cstdio>

using namespace std;

const int N = 100001;
int n, q;
int a[N];


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", &q);
  while (q--) {
    int t, x, s = -1, l = 1, r = n;
    scanf("%d %d", &t, &x);
    if (t == 0) {
      while (l <= r) {
        int m = (l + r) / 2;
        if (a[m] == x)
          s = m;
        if (a[m] <= x)
          l = m + 1;
        else
          r = m - 1;
      }
    }
    if (t == 1) {
      while (l <= r) {
        int m = (l + r) / 2;
        if (a[m] <= x) {
          s = m;
          l = m + 1;
        } else
          r = m - 1;
      }
    }
    if (t == 2) {
      while (l <= r) {
        int m = (l + r) / 2;
        if (a[m] >= x) {
          s = m;
          r = m - 1;
        } else
          l = m + 1;
      }
    }
    printf("%d\n", s);
  }

  return 0;
}