#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 u, int n) {
    int m,p=1;
    while (p<u){
        m=(p + u)/2;
        if(v[m]<=n)
            p=m+1;
        else
            u=m;
    }

    m=(p + u)/2;
    if (v[m] >n)
       -- m;
    return m;
}

int c2(int u, int n) {
    int m,p=1;
    while (p<u) {
        m=(p+u)/2;
        if (v[m]<n)
            p=m+1;
        else
            u=m;
    }
    
    m=(p + u) / 2;
    if (v[m]<n)
       m++;
    return m;
}
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(n,b)<<endl;
    else
      out<<c2(n,b);
}
    return 0;
}