#include <iostream>
#include <fstream>
#define bound 100000

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
unsigned int A[bound];
int n, m;

void binsearch0(unsigned int x){
  int lo = 0;
  int hi = n-1;
  int mid;
  while(lo <= hi){
    mid = lo + (hi - lo) / 2;
    if(A[mid] <= x) lo = mid + 1;
    else hi = mid - 1;
  }
  mid = lo + (hi - lo) / 2;
  if(A[mid] > x) mid--;
  if(A[mid] == x){ fout <<  mid + 1 << endl; return;};
  fout <<  -1 << endl;
}

void binsearch1(unsigned int x){
  int lo = 0;
  int hi = n-1;
  int mid;
  while(lo < hi){
    mid = lo + (hi - lo) / 2;
    if(A[mid] <= x) lo = mid + 1;
    else hi = mid;
  }
  mid = lo + (hi - lo) / 2;
  if(A[mid] > x ) mid--;
  fout << mid + 1 << endl;
}

void binsearch2(unsigned int x){
  int lo = 0;
  int hi = n-1;
  int mid;
  while(lo < hi){
    mid = lo + (hi - lo) / 2;
    if(A[mid] < x) lo = mid + 1;
    else hi = mid; 
  }
  mid = lo + (hi - lo) / 2;
  if(A[mid] < x) mid++;
  fout <<  mid + 1 << endl;
}    

void question(int q, unsigned int x){
  if(q == 0) binsearch0(x);
  else if(q == 1) binsearch1(x);
  else binsearch2(x);
}

int main(){
  fin >> n;
  for(int i = 0; i<n; i++)
    fin >> A[i];
  fin >> m;  
  for(int i = 0; i<m ;i++){
    int q;
    unsigned int x;
    fin >> q >> x;
    question(q, x);
  }
}