#include <iostream>
#include <fstream>

std::ifstream in("cautbin.in");
std::ofstream out("cautbin.out");

unsigned int v[100000];
int N, M;

void cautbin0(unsigned int x){
  int st = 0, dr = N-1;
  bool isTrue = false;
  int poz = -1;
  int med;
  while(st < dr){
    med = st + (dr - st) / 2; 
    if(v[med] == x){
      isTrue = true;
      if(med > poz) poz = med;
      st = med + 1;
    }
    else if(v[med] < x) st = med + 1;
    else dr = med - 1;
  }
   if(st == dr)
    if(v[med] == x)
      {
        isTrue = true;
        if(med > poz) poz = med;
      }
   if(isTrue == true) out << poz + 1 << std::endl;
   else out << -1 << std::endl;
}

void cautbin1(unsigned int x){
  int st = 0, dr = N-1, med;
  int poz = -1;
  while(st < dr){
    med = st + (dr - st) / 2;
    if(v[med] <= x){
      if(med > poz) poz = med;
      if(v[med+1] <= x) st = med + 1;
      else dr = med - 1;
    }
    else if(v[med] > x){
      dr = med - 1;
    }
  }
  if(st == dr)
    if(v[med] <= x)
      if(med > poz) poz = med;
  out << poz + 1<< std::endl;
}

void cautbin2(unsigned int x){
  int st = 0, dr = N-1, med;
  unsigned int poz = 1000010;
  while(st < dr){
    med = st + (dr - st) / 2;
    if(v[med] >= x){
      if(med < poz) poz = med;
      dr = med - 1;
    }
    else if(v[med] < x) st = med+1;
  }
  if(st == dr)
    if(v[st] >= x)
      if(st < poz) poz = st;
  out << poz + 1 << std::endl;
}

int main(){
  in >> N;
  for(int i = 0; i<N; i++) in >> v[i];
  in >> M;
  while(M--){
    int caz, x;
    in >> caz >> x;
    if(caz == 0) cautbin0(x);
    if(caz == 1) cautbin1(x);
    if(caz == 2) cautbin2(x);
  }
}