#include <fstream>
using namespace std;
ifstream in ("cautbin.in");
ofstream out ("cautbin.out");
int v[100001];
int cautbin(int b,int n){
    long long st=1,dr=n,mijl,poz=-1;
    while(st<=dr){
        mijl=(st+dr)/2;
        if(b==v[mijl]){
            poz=mijl;
            break;
        }
        else if (b<v[mijl])
        dr=mijl-1;
        else
        st=mijl+1;
    }
   return poz;
}
int c1(int b,int n){
     long long st=1,dr=n,mijl;
    while(st<dr){
        mijl=(st+dr)/2;
     if (b>=v[mijl])
        dr=mijl;
        else
        st=mijl+1;
    }
   mijl=(st+dr)/2;
   if (b<v[mijl])
   mijl--;
   return mijl;
}
int c2(int b,int n){
     long long st=1,dr=n,mijl;
    while(st<dr){
        mijl=(st+dr)/2;
        if (b>v[mijl])
        dr=mijl;
        else
        st=mijl+1;
    }
   mijl=(st+dr)/2;
   if (b>v[mijl])
   mijl++;
   return mijl;
}
int main()
{long long n,c,a,b,i,x;
in>>n;
for(i=1; i<=n; i++)
    in>>v[i];
in>>c;
for(i=1; i<=c; i++){
    in>>a>>b;
    if(a==0){
     if(cautbin(b,n)==-1)
     out<<-1<<endl;
     else{
         long long  y=cautbin(b,n),cn=n;
         while(cn>=y){
             if(v[cn]==b){
                 out<<cn<<endl;
                 break;
             }
             cn--;
         }
     }
    }
    else if (a==1)
           out<<c1(b,n)<<endl;
    else
      out<<c2(b,n);
}
    return 0;
}