#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;

int N, M, x, val, ans;
const int Nmax = 100555;

int A[Nmax];

int bin1(int val) {
  int l = 0, h = N-1;
  while(h > l) {
    int m = (l + h)/2 + 1;

    if (A[m] <= val) {
      l = m;
    } else h = m - 1;
  }
  return l;
}

int bin2(int val) {
  int l = 0, h = N-1;
  while(h > l) {
    int m = (l+h)/2;

    if (A[m] >= val) {
      h = m;
    } else l = m + 1;
  }
  return l;
}

int main() {
  fin >> N;
  for(int i = 0; i < N; ++i)
    fin >> A[i];


  fin >> M;
  while(M--) {
    fin >> x >> val;
    switch(x) {
      case 0: ans = bin1(val); fout << (A[ans] == val ? ans + 1 : -1) << '\n'; break;
      case 1: fout << bin1(val) + 1 << '\n'; break;
      case 2: fout << bin2(val) + 1 << '\n'; break;
    }
  }

  return 0;
}