#include <fstream>
#define NMAX 100002
using namespace std;
ifstream fin ("cautbin.in");
ofstream fout ("cautbin.out");

int v[NMAX];
int N;
int cautare0 (int x){

  int st = 1;
  int dr = N;
  int mid;
  int poz = -1;
  while (st <= dr){
    mid = (st+dr)/2;
    if (v[mid]==x) poz = mid;
    if (v[mid]<=x)
      st = mid + 1;
    else
      dr = mid - 1;
  }
  return poz;
}

int cautare1 (int x){

  int st = 1;
  int dr = N;
  int mid;
  int poz;
  while (st <= dr){
    mid = (st+dr)/2;
    if (v[mid]<=x){
      st = mid + 1;
      poz = mid;
    }
    else
      dr = mid - 1;
  }
  return poz;
}

int cautare2(int x){
  int st = 1;
  int dr = N;
  int mid;
  int poz;
  while (st <= dr){
    mid = (st+dr)/2;
    if (v[mid]>=x){
      dr = mid - 1;
      poz = mid;
    }
    else
      st = mid + 1;
  }
  return poz;
}


int main (){


  fin >> N;
  for (int i = 1; i <= N; ++i)
    fin >> v[i];

  int M,tip,nr;
  fin >> M;
  for (int i = 1; i <= M; ++i){
    fin >> tip >> nr;
    if (tip == 0) fout << cautare0(nr) << "\n";
    else if (tip == 1) fout << cautare1(nr) << "\n";
    else if (tip == 2) fout << cautare2(nr) << "\n";
  }


}