#include <fstream>
#define ll long long
using namespace std;

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

 int n;
 ll mid, v[100000];

ll caut( ll st, ll dr, ll x){
    ll save=-1;
while ( st<= dr ) {
  ll mid= ( st + dr ) /2;
  if ( x>=v[mid] ) st=mid+1; else dr=mid-1;
  if ( x==v[mid]  ) save=mid  ;
}
 return save;
}
ll caut1( ll st, ll dr, ll x){
    ll save;
while ( st<= dr ) {
  ll mid= ( st + dr ) /2;
  if ( x>=v[mid] ) st=mid+1; else dr=mid-1;
  if ( x>=v[mid]  ) save=mid  ;
}
 return save;
}
ll caut2( ll st, ll dr, ll x){
    ll save;
while ( st<= dr ) {
  ll mid= ( st + dr ) /2;
  if ( x>v[mid] ) st=mid+1; else dr=mid-1;
  if ( x<=v[mid]  ) save=mid  ;
}
 return save;
}



int main()
{
    in>>n;
    for(int i=1; i<=n; i++)
        in>>v[i];
   int nr; in>>nr;
   ll x;

 for(int i=1; i<=nr; i++){
        int a; in>>a>>x;
        if ( a==0 ) out<<caut(1,n,x)<<'\n';
        if ( a==1) out << caut1(1,n,x)<<'\n';
        if ( a==2 ) out<<caut2(1,n,x)<<'\n';
       }

    return 0;
}