#include <iostream>
#include <fstream>
using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int n, m, q, x, v[100005];

int binarySearch(int v[], int lo, int hi, int x) {
  if (lo > hi) {
    return -1;
  }
  
  int mid = lo + (hi - lo) / 2;
  if (v[mid] == x) {
    return mid;
  }
  if (v[mid] > x) {
    return binarySearch(v, lo, mid - 1, x);
  }
  if (v[mid] < x) {
    return binarySearch(v, mid + 1, hi, x);
  }
  
  return -1;
}

int solveFirstCase(int x) {
  int index = binarySearch(v, 1, n, x);
  ++index;
  while (index && v[index] == x) {
    ++index;
  }
  return index - 1;
}

int solveSecondCase(int x) {
  int index = binarySearch(v, 1, n, x);
  if (index == -1) {
    --x;
    int q_index = solveFirstCase(x);
    while (q_index == -1) {
      --x;
      q_index = solveFirstCase(x);
    }
    return q_index;
  } else {
    return solveFirstCase(x);
  }
}

int solveThirdCase(int x) {
  int index = binarySearch(v, 1, n, x);
  if (index == -1) {
    ++x;
    int q_index = binarySearch(v, 1, n, x);
    while (q_index == -1) {
      ++x;
      q_index = binarySearch(v, 1, n, x);
    }
    q_index--;
    while (v[q_index] == x) {
      q_index--;
    }
    return q_index + 1;
  } else {
    index--;
    while (v[index] == x) {
      --index;
    }
    return index + 1;
  }
}

int main() {
  f >> n;
  for (int i = 1; i <= n; i++) {
    f >> v[i];
  }
  f >> m;
  while (m--) {
    f >> q >> x;
    if (q == 0) {
      g << solveFirstCase(x);
    } else if (q == 1) {
      g << solveSecondCase(x);
    } else {
      g << solveThirdCase(x);
    }
    g << "\n";
  }
}