#include <fstream>
using namespace std;

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

    int n, m;
    fin >> n;

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

    fin >> m;
    while (m--) {
        int t, x;
        fin >> t >> x;
        
        int st = 0, dr = n - 1;
        int m, poz = -1;
        switch (t) {
            case 0:
                while (st <= dr) {
                    m = st + (dr - st) / 2;
                    if (v[m] <= x) {
                        if (v[m] == x)
                        poz = m;
                        st = m + 1;
                    } else {
                        dr = m - 1;
                    }
                }
                break;
            case 1:
                while (st <= dr) {
                    m = st + (dr - st) / 2;
                    if (v[m] <= x) {
                        poz = m;
                        st = m + 1;
                    } else {
                        dr = m - 1;
                    }
                }
                break;
            case 2:
                while (st <= dr) {
                    m = st + (dr - st) / 2;
                    if (v[m] >= x) {
                        poz = m;
                        dr = m - 1;
                    } else {
                        st = m + 1;
                    }
                    
                }
                break;
        }
        fout << (poz == -1 ? -1 : poz + 1) << endl;
    }

    return 0;
}