#include <algorithm>
#include <bitset>
#include <cmath>
#include <fstream>
#include <iostream>
#include <queue>
#include <stack>
#include <string.h>
#include <string>
#include <vector>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
ifstream fin ("cautbin.in");
ofstream fout ("cautbin.out");
const int INF = 0x3f3f3f3f;
const int Nmax = 100555;

int a[Nmax];

int main() {
  int N, M, c, x, pos;
  fin >> N;
  for(int i = 0; i < N; ++i)
    fin >> a[i];
  fin >> M;
  while(M--) {
    fin >> c >> x;
    if (c == 1) {
      pos = upper_bound(a, a+N, x) - a;
      fout << pos << '\n';
    } else if (c == 2) {
      pos = lower_bound(a, a+N, x) - a;
      fout << pos + 1 << '\n';
    } else if (c == 0) {
      pos = upper_bound(a, a+N, x) - a;
      if (pos == 0)
        fout << -1 << '\n';
      else {
        --pos;
        if (a[pos] == x)
          fout << pos+1 << '\n';
        else
          fout << -1 << '\n';
      }
    }
  }

  return 0;
}