#include <iostream>
#include <fstream>
using namespace std;

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

int v[1000005];
int n, m;

int BinSearch0(int x) {
    int lf = 1;
    int rg = n;


    while (lf <= rg) {
        int mid = lf + (rg - lf) / 2;

        if (x < v[mid]) {
            rg = mid - 1;
        }
        else {
            lf = mid + 1;
        }
    }

    return lf - 1;
}

int BinSearch1(int x) {
    int lf = 1;
    int rg = n;

    while (lf < rg) {
        int mid = (lf + rg) / 2;

        if (x <= v[mid]) {
            rg = mid;
        }
        else {
            lf = mid + 1;
        }
    }

    return lf;
}


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

    fin >> m;
    for (int i = 0 ; i < m; i++) {
        int task, x;
        fin >> task >> x;
        if (task == 0) {
            int idx = BinSearch0(x);
            if (v[idx] == x) {
                fout << idx << '\n';
            }
            else {
                fout << -1 << '\n';
            }
        }
        else if (task == 1) {
            int idx = BinSearch0(x);
            fout << idx << '\n';
        }
        else if (task == 2) {
            int idx = BinSearch1(x);
            fout << idx << '\n';
        }

    }
    return 0;
}