#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int left_most(int a[], int n, int T) {
  int L = 0, R = n - 1;
  while (L < R) {
    int m = L + (R - L) / 2;
    if (a[m] < T)
      L = m + 1;
    else
      R = m;
  }
  return L;
}
int right_most(int a[], int n, int T) {
  int L = 0, R = n - 1;
  while (L < R) {
    int m = L + (R - L) / 2;
    if (a[m] <= T)
      L = m + 1;
    else
      R = m;
  }
  return L - 1;
}
int classic(int a[], int n, int T) {
  int st = 0, dr = n - 1;
  while (st <= dr) {
    int m = st + (dr - st) / 2;
    if (a[st] == T)
      return st;
    else if (a[m] > T)
      dr = m - 1;
    else
      st = m + 1;
  }
  return -1;
}
int sir[100001], N, M;
int main() {
  fin >> N;
  for (int i = 0; i < N; i++)
    fin >> sir[i];
  fin >> M;
  for (int i = 0; i < M; i++) {
    int x, y;
    fin >> x >> y;
    if (x == 0) {
      if (classic(sir, N, y) == -1)
        fout << -1 << "\n";
      else
        fout << classic(sir, N, y) + 1 << "\n";
    } else if (x == 1) {
      fout << right_most(sir, N, y) + 1 << "\n";
    } else {
      fout << left_most(sir, N, y) + 1 << "\n";
    }
  }
  fin.close();
  fout.close();
  return 0;
}