#include <fstream>
using namespace std;
 ifstream in("cautbin.in");
 ofstream out("cautbin.out");
 int n,mid, v[100000];
 int caut(int st,int dr,int x)
 {
     int save=-1;
     while(st<=dr)
     {
          mid=(st+dr)/2;
         if(x>=v[mid]) st=mid+1; else dr=mid-1;
         if(x==v[mid]) save=mid;
     }
     return save;
 }
  int caut1(int st,int dr,int x)
 {
     int save;
     while(st<=dr)
     {
          mid=(st+dr)/2;
         if(x>=v[mid]) st=mid+1; else dr=mid-1;
         if(x>=v[mid]) save=mid;
     }
     return save;
 }
  int caut2(int st,int dr,int x)
 {
     int save;
     while(st<=dr)
     {
          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;
   int 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;
}