#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];

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

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

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

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;
}