#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int a[10000000],n;
int caut2(int d)
{
    long st,dr,last,med;
    st=1;
    dr=n;
    last=-1;
    while (st<=dr){
        med=(st+dr)/2;
        if (a[med]<d)
            st=med+1;
        else
        {
            last=med;
            dr=med-1;
        }
    }
    return last;
}
int caut1(int d)
{
    long st,dr,last,med;
    st=1;
    dr=n;
    last=-1;
    while (st<=dr){
        med=(st+dr)/2;
        if (a[med]<=d)
           {
               st=med+1;
               last=med;
           }
        else
        {
            dr=med-1;
        }
    }
    return last;
}
int main()
{
    long i,m,c,d;
    fin>>n;
    for (i=1;i<=n;i++)
        fin>>a[i];
    fin>>m;
    for (i=1;i<=m;i++){
        fin>>c>>d;
        if (c==0 || c==1)
            fout<<caut1(d)<<"\n";
        else
            fout<<caut2(d)<<"\n";
    }
    return 0;
}