#include <cstdio>
#include <algorithm>
using namespace std;
const int NMAX = 100505;
const int INF = 0x3f3f3f3f;
int n, m, A[NMAX];

void read() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++)
    scanf("%d", &A[i]);
  A[n + 1] = INF;
}

// largest pos <= val
// invariant: A[left] <= X < A[right]
int bsearch(int val) {
  int left = 0, right = n + 1;
  while (right - left > 1) {
    int mid = left + (right - left) / 2;
    if (A[mid] <= val)
      left = mid;
    else
      right = mid;
  }
  return left;
}

void solve() {
  int type, x;
  
  scanf("%d", &m);
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &type, &x);
        
    switch (type) {
      case 0: {
        int pos = bsearch(x);
        printf("%d\n", (pos && A[pos] == x) ? pos : -1);
        break ;
      }
      case 1: {
        int pos = bsearch(x);
        printf("%d\n", pos);
        break ;
      }
      case 2: {
        int pos = bsearch(x - 1) + 1;
        printf("%d\n", pos);
        break ;
      }
    }
  }
}

int main() {
  freopen("cautbin.in", "r", stdin);
  freopen("cautbin.out", "w", stdout);
  
  read();
  solve();
  return 0;
}