#include <fstream>
#include <bitset>

using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");

const int N = 1e5 + 5;
int n, i, m, task, val;
int v[N], ans[5], ans1[5];

int bsearch0(int st, int dr, int x)
{
    int mij;
    while(st <= dr)
    {
        mij = st + (dr - st) / 2;
        if(v[mij] <= x)
            st = mij + 1;
        else
            dr = mij - 1;
    }
    while(v[mij] != x && mij >= 1)
        mij--;
    if(v[mij] == x)
        return mij;
    else
        return -1;
}

int bsearch1(int st, int dr, int x)
{
    int mij;
    while(st < dr)
    {
        mij = st + (dr - st) / 2;
        if(v[mij] <= x)
            st = mij + 1;
        else
            dr = mij;
    }
    while(v[mij] > x && mij >= 1)
        mij--;
    return mij;
}

int bsearch2(int st, int dr, int x)
{
    int mij;
    while(st < dr)
    {
        mij = st + (dr-st) / 2;
        if(v[mij] >= x)
            dr = mij;
        else
            st = mij + 1;
    }
    while(v[mij] < x && mij >= 1)
        mij++;
    return mij;
}

int main()
{
    in >> n;
    for(i = 1; i <= n; i++)
        in >> v[i];

    in >> m;
    while(m--)
    {
        in >> task >> val;
        if(task == 0) out << bsearch0(1, n, val) << '\n';
        else if(task == 1) out<<bsearch1(1, n, val) << '\n';
        else if(task == 2) out<<bsearch2(1, n, val) << '\n';
    }

    return 0;
}