#include <fstream>

using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");
int i,n,m,v[100001],a,b;
int cb(int p,int u,int val)
{
    int mij;
    while(p<=u)
    {
        mij=(p+u)/2;
        if(v[mij]>val) u=mij-1;
        else p=mij+1;
    }
    mij=(u+p)/2;
    if(v[mij]>val) mij--;
    if(v[mij]==val) return mij;
    return -1;
}
int cb1(int p, int u, int val)
{
    int mij;
    while(p<u)
    {
        mij=(p+u)/2;
        if(v[mij]<=val) p=mij+1;
        else u=mij;
    }
    mij=(p+u)/2;
    if(v[mij]>val) mij--;
    return mij;
}
int cb2(int p, int u, int val)
{
    int mij;
    while(p<u)
    {
        mij=(p+u)/2;
        if(v[mij]<val) p=mij+1;
        else u=mij;
    }
    mij=(p+u)/2;
    if(v[mij]<val) mij++;
    return mij;
}
int main()
{
    f>>n;
    for(i=1;i<=n;++i) f>>v[i];
    f>>m;
    while(m--)
    {
        f>>a>>b;
        if(a==0) g<<cb(1,n,b)<<"\n";
        else if(a==1) g<<cb1(1,n,b)<<"\n";
        else if(a==2) g<<cb2(1,n,b)<<"\n";
    }
}