#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 poz = -1;
  while(lo < hi){
    int mid = lo + (hi - lo) / 2;
    if(A[mid] == x){
      lo = mid+1;
      poz = mid;
    }
    else if(A[mid] < x) lo = mid+1;
    else hi = mid-1;
  }
  if(A[lo] == x && lo > poz) poz = lo;
  if(A[hi] == x && hi > poz) poz = hi;
  fout << poz + 1 << endl;
}

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

  fout << poz + 1 << endl;
}

void binsearch2(unsigned int x){
  int lo = 0;
  int hi = n-1; 
  int poz = -1;
  while(lo < hi){
    int mid = lo + (hi - lo) / 2;
    if(A[mid] == x){
      if(A[mid-1] == x){
        poz = mid - 1;
        hi = mid - 1;
      }
      else lo = mid + 1;
    }
    else if(A[mid] > x) hi = mid - 1;
    else lo = mid + 1;
  }
  if(A[lo] >= x && lo < poz) poz = lo;
  if(A[hi] >= x && hi < poz) poz = hi;
  fout << poz + 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);
  }
}