#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n, v[100002];

void Read(){
    fin >> n;
    for(int i = 1; i <= n; i++)
      fin >> v[i];	
}

int solve0(int nr){
  int Left=0, Right = n, Mid, sol = -1;
  while(Left <= Right){
    Mid = (Left + Right) / 2;
    if(v[Mid] == nr){
      sol = Mid;
      Left = Mid + 1;
    }
    else if(v[Mid] > nr)
      Right = Mid - 1;
    else
      Left = Mid + 1;
      
  }
  return sol;
}

int solve1(int nr){
  int Left=0, Right = n, Mid, sol = -1;
  while(Left <= Right){
    Mid = (Left + Right) / 2;
    if(v[Mid] > nr)
      Right = Mid - 1;
    else if(v[Mid] <= nr){
      sol = Mid;
      Left = Mid + 1;
    }
  }
  return sol;
}

int solve2(int nr){
  int Left=0, Right = n, Mid, sol = -1;
  while(Left <= Right){
    Mid = (Left + Right) / 2;
    if(v[Mid] >= nr){
      sol = Mid;
      Right = Mid - 1;
    }
    else if(v[Mid] <= nr)
      Left = Mid + 1;
  }
  return sol;
}

void Solve(){
  int nr, q, nq;
  fin >> nq;
  for(int i = 1; i <=nq; ++i){
    fin >> q >> nr;
    if(q == 0)
      fout << solve0(nr) << "\n";
    else if(q == 1)
      fout << solve1(nr) << "\n";
    else if(q == 2)
      fout << solve2(nr) << "\n";
  }	
}
int main(){
    Read();
    Solve();
}