#include <iostream>
#include <fstream>
#define NMax 100001
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int q,n,m,i,j,X,Y,st,dr,v[NMax];
int caut_binar0(int p,int u,int k)
{
    int m,n=u;
    while(p<u)
    {
        m=(p+u)/2;
        if(v[m]<=k)
        {
            p=m+1;
        }
        else u=m-1;
    }
    m=(p+u)/2;
    if(v[m]>k) m--;
    if(v[m]==k) return m;
    return -1;
};
int caut_binar1(int p,int u,int k)
{
    int m,n=u;
    while(p<u)
    {
        m=(p+u)/2;
        if(v[m]<=k)
            p=m+1;
        else u=m;
    }
    m=(p+u)/2;
    if(v[m]>k) m--;
    return m;
};
int caut_binar2(int p,int u,int k)
{
    int m;

    while (p < u) {
        m = (p + u) / 2;
        if (v[m] < k)
            p = m + 1;
        else
            u = m;
    }

    m = (p + u) / 2;
    if (v[m] < k)
       ++ m;
    return m;

};
int main()
{
fin>>n;
for(i=1;i<=n;i++)
{
    fin>>v[i];
}
fin>>m;
for(q=1;q<=m;q++)
{
    fin>>X>>Y;
    if(X==0)
        fout<<caut_binar0(1,n,Y)<<"\n";
    else if(X==1)
        fout<<caut_binar1(1,n,Y)<<"\n";
    else if(X==2)
        fout<<caut_binar2(1,n,Y)<<"\n";
}
    return 0;
}