#include <iostream>
#include<fstream>
#include<cmath>
using namespace std;
int proc0(int w, int b[], int s, int d);
int proc1(int w, int b[],int s, int d);
int proc2(int w, int b[], int s, int d);

int main() {
   ifstream intr("cautbin.in");
   ofstream exte("cautbin.out");
   int n,m,v,p;
   intr>>n;
   int a[n+1];
   for (int i=1; i<=n; i++) intr>>a[i];
   intr>>m;
   for (int i=0; i<m; i++) {
            intr>>v>>p;
            if (v==0) exte<<(proc0(p,a,1,n))<<"\n";
            else
            if (v==1) exte<<(proc1(p,a,1,n))<<"\n";
            else exte<<(proc2(p,a,1,n))<<"\n";}
   intr.close(); exte.close();
  // cin.ignore(1);
   return(0); 
  }


int proc0(int w, int b[],int s,int d)
{ int mij;
  while (s<=d) {
        mij=s+(d-s)/2;
        if (b[mij]<=w) s=mij+1;
        else d=mij-1;
  }
  if (b[mij]>=w) mij--;
  if (b[mij]==w) return(mij);
  else return(-1);
  }
int proc1(int w, int b[],int s, int d)
{ int m;
  while (s<d) {
        m=s+(d-s)/2;
        if(b[m]<=w) s=m+1;
        else d=m;}
  m=s+(d-s)/2;
  if (b[m]>w) m--;
  return(m);}
  
int proc2(int w, int b[], int s, int d)
{ int m;
  while (s<d) {
        m=s+(d-s)/2;
        if(b[m]<w) s=m+1;
        else d=m;}
  m=s+(d-s)/2;
  if (b[m]>w) m++;
  return(m);
  }