#include <iostream>
#include <fstream>

using namespace std;

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

int v[100001];

int cautare_binara0(int st, int dr, int x)
{
    int mij;

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

    return -1;
}

int cautare_binara1(int st, int dr, int x)
{
    int mij, p = -1;

        while(st <= dr) {
            mij = (st + dr) / 2;
            if(v[mij] > x)
                dr = mij - 1;
            else {
                st = mij + 1;
                p = mij;
            }
        }

    return p;
}

int cautare_binara2(int st, int dr, int x)
{
    int mij, p = -1;

        while(st <= dr) {
            mij = (st + dr) / 2;
            if(v[mij] < x)
                st = mij + 1;
            else {
                dr = mij - 1;
                p = mij;
            }
        }

    return p;
}
int main(void)
{
    int n, m, tip, x;

    fin >> n;

    for(int i = 1; i <= n; i++)
        fin >> v[i];

    fin >> m;

    for(int i = 1; i <= m; i++) {
        fin >> tip >> x;
        if(tip == 0)
            fout << cautare_binara0(1, n, x) << '\n';
        else if(tip == 1)
            fout << cautare_binara1(1, n, x) << '\n';
        else
            fout << cautare_binara2(1, n, x) << '\n';
    }

    return 0;
}