#include <fstream>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int a[100001], n;

void cautbin0(int x)
{
    int st, dr, mij, poz;
    poz = -1;
    st = 1;
    dr = n;
    while(st<=dr)
    {
        mij = (st+dr)/2;
        if(x==a[mij])
        {
            poz = mij;
            st = mij+1;
        }
        else if(x<a[mij])
                dr = mij-1;
             else st = mij+1;
    }
    fout << poz << "\n";
}

void cautbin1(int x)
{
    int st, dr, mij, poz;
    poz = -1;
    st = 1;
    dr = n;
    while(st<=dr)
    {
        mij = (st+dr)/2;
        if(a[mij]<=x)
        {
            poz = mij;
            st = mij+1;
        }
        else dr = mij-1;
    }
    fout << poz << "\n";
}

void cautbin2(int x)
{
    int st, dr, mij, poz;
    poz = -1;
    st = 1;
    dr = n;
    while(st<=dr)
    {
        mij = (st+dr)/2;
        if(a[mij]>=x)
        {
            poz = mij;
            dr = mij-1;
        }
        else st = mij+1;
    }
    fout << poz << "\n";
}

int main()
{
    int i, m, t, x;
    fin >> n;
    for(i=1; i<=n; i++)
        fin >> a[i];

    fin >> m;
    for(i=1; i<=m; i++)
    {
        fin >> t >> x;
        if(t==0) cautbin0(x);
        else if(t==1) cautbin1(x);
             else cautbin2(x);
    }
    return 0;
}