#include <fstream>
using namespace std;

int n,m,v[100000],tip,val;
int bsearch0(int l, int h, int t)
{
    int mid;
    while(l<=h)
    {
        mid=(l+h)/2;
        if(v[mid]<=t)
            l=mid+1;
        else
            h=mid-1;
    }
    mid=(l+h)/2;
    if(v[mid]>t) mid--;
    if(v[mid]==t) return mid;
    return -1;
}
int bsearch1(int l, int h, int t)
{
    int mid;
    while(l<=h)
    {
        mid=(l+h)/2;
        if(v[mid]<=t)
            l=mid+1;
        else
            h=mid-1;
    }
    mid=(l+h)/2;
    if(v[mid]>t) mid--;
    return mid;
}
int bsearch2(int l, int h, int t)
{
    int mid;
    while(l<h)
    {
        mid=(l+h)/2;
        if(v[mid]<t)
            l=mid+1;
        else
            h=mid-1;
    }
    mid=(l+h)/2;
    if(v[mid]<t) mid++;
    return mid;
}
int main ()
{
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    fin>>n;
    for (int i=1;i<=n;i++)
        fin>>v[i];
    fin>>m;
    while(m!=0)
    {
        fin>>tip>>val;
        if(tip==0)
        fout<<bsearch0(1,n,val)<<endl;
        if(tip==1)
        fout<<bsearch1(1,n,val)<<endl;
        if(tip==2)
        fout<<bsearch2(1,n,val)<<endl;
        m--;
    }
    fin.close();
    fout.close();
}