#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int cautBinUpper(const vector<int>& v, int val) {
  int left = 0;
  int right = (int)v.size() - 1;
  int mid;
  while (left <= right) {
    mid = left + (right - left) / 2;
    if (v[mid] <= val)
      left = mid + 1;
    else
      right = mid - 1;
  }
  return right;
}

int cautBinLower(const vector<int>&v, int val) {
  int left = 0;
  int right = (int)v.size() - 1;
  int mid;
  while (left <= right) {
    mid = left + (right - left) / 2;
    if (v[mid] >= val)
      right = mid - 1;
    else
      left = mid + 1;
  }
  return left;
}

int main() {
  freopen("cautbin.in", "r", stdin);
  freopen("cautbin.out", "w", stdout);

  int N;
  scanf("%d", &N);

  vector<int> v(N);
  for (int i = 0; i < N; ++i)
    scanf("%d", &v[i]);

  int Q, op, val;
  scanf("%d", &Q);
  for (int i = 0; i < Q; ++i) {
    scanf("%d%d", &op, &val);
    if (op == 0) {
      int position = cautBinUpper(v, val);
      if (position >= 0 && v[position] == val)
	printf("%d\n", position + 1);
      else
	printf("-1\n");
      continue;
    }
    if (op == 1) {
	printf("%d\n", cautBinUpper(v, val) + 1);
	continue;
    }
    printf("%d\n", cautBinLower(v, val) + 1);
  }
  
  return 0;
}