#include <iostream>
#include <fstream>
using namespace std;
#define dim 100009

ifstream in("cautbin.in");
ofstream out("cautbin.out");
int n,m;
int v[dim];
int op,x;

int cb0(int st, int dr){
   int mij;
   while(st<=dr){
      mij =(dr + st)/2;
      if(v[mij]<=x) st=mij+1;
      else dr=mij-1;
   }
   mij=(st+dr)/2;
   if(v[mij]>x) mij--;
   if(v[mij]==x) return mij;
   return -1;

}

int cb1(int st, int dr){
   int mij;
   while(st<dr){
    mij=(st+dr)/2;
    if(v[mij]<=x) st=mij+1;
    else dr=mij;
   }
   mij=(st+dr)/2;
   if(v[mij]>x) mij--;
   return mij;

}

int cb2(int st, int dr){
   int mij;
   while(st<dr){
      mij=(st+dr)/2;
      if(v[mij]<x) st=mij+1;
      else dr = mij;
   }
   mij=(st+dr)/2;
   if(v[mij]<x) mij++;
   return mij;

}

int main()
{
    in>>n;
    for(int i=1;i<=n;i++) in>>v[i];
    in>>m;
    while(m){
        in>>op>>x;
        if(op==0) out<<cb0(1,n)<<'\n';
        if(op==1) out<<cb1(1,n)<<'\n';
        if(op==2) out<<cb2(1,n)<<'\n';
       m--;
    }
    return 0;
}