#include <fstream>
#include <iostream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int N, i, M, a[100001], tip, x;
int cautbin(int x,int i, int j, int tip) {
  if (i == j){
    if ( tip == 0 && a[i] != x)
        return -1;
    return i;
    }
  else{
    int mij = (i+j) / 2;
    if( ( tip == 0 && a[mij+1] <= x) || ( tip == 1 && a[mij+1] <= x) || ( tip == 2 && a[mij]<x) )
            return cautbin(x,mij+1,j,tip);
        else
            return cautbin(x,i,mij,tip);
    }
}

int main() {
  cin >> N;
  for ( i = 1; i<=N; i++ )
    cin >> a[i];
  cin >> M;
  for ( i = 1; i <= M; i++ ){
    cin >> tip >> x;
    cout << cautbin(x, 1, N, tip) << '\n';
  }
}