#include <iostream>
#include <fstream>
#define N 100010
int v[N];
using namespace std;

int cb0(int st, int dr, int val, int n)
{
    if (st <= dr)
    {
        int mij = st + (dr - st)/2;
        if (v[mij] == val)
            if (mij == n || v[mij + 1] != val)
                return mij;
            else return cb0(mij + 1, dr, val, n);
        else
            if (v[mij] > val)
                return cb0(st, mij - 1, val, n);
        else
            return cb0(mij + 1, dr, val, n);

    }
    else return -1;
}

int cb1(int st, int dr, int val, int n)
{
    if (st <= dr)
    {
        int mij = st + (dr - st)/2;
        if (v[mij] <= val)
            if (mij == n || v[mij + 1] > val)
                return mij;
            else return cb1(mij + 1, dr, val, n);
        else
            return cb1(st, mij - 1, val, n);

    }
    else return -1;
}

int cb2(int st, int dr, int val, int n)
{
    if (st <= dr)
    {
        int mij = st + (dr - st)/2;
        if (v[mij] >= val)
            if (mij == 1 || v[mij - 1] < val)
                return mij;
            else return cb2(st, mij - 1, val, n);
        else
            return cb2(mij + 1, dr, val, n);

    }
    else return -1;
}

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

    int n, i, x, m, opt;
    fin >> n;
    for (i = 1; i <= n; i++)
        fin >> v[i];
    fin >> m;
    for (i = 1; i <= m; i++)
    {
        fin >> opt >> x;
        if (opt == 0)
            fout << cb0(1, n, x, n) << '\n';
        else
            if (opt == 1)
                fout << cb1(1, n, x, n) << '\n';
        else
            if (opt == 2)
                fout << cb2(1, n, x, n) << '\n';
    }

    fin.close();
    fout.close();


    return 0;
}