#include <fstream>
#define NMax 100010

using namespace std;
long int n, m, v[NMax], tip, x;
int cautbin() {
    long int st = 1, dr = n, mid;
    while (st <= dr) {
        mid = st + (dr-st)/2;
        if (v[mid] < x)
            st = mid + 1;
        else if (v[mid] > x)
            dr = mid - 1;
        else
            if (tip == 0) {
                while (v[mid] == x)
                    ++mid;
                return --mid;
            }
            else if (tip == 1) {
                while (v[mid] == x)
                    ++mid;
                return --mid;
            }
            else if (tip == 2) {
                while (v[mid] == x)
                    --mid;
                return ++mid;
            }
    }
    if (tip == 0)
        return -1;
    else if (tip == 1)
        return dr;
    else
        return st;

}
int main()
{
    ifstream fin ("cautbin.in");
    ofstream fout ("cautbin.out");
    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> v[i];
    fin >> m;
    for (int i = 1; i <= m; ++i) {
        fin >> tip >> x;
        fout << cautbin() << "\n";
    }
    return 0;
}