#include <iostream>
#include <fstream>

using namespace std;

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

int v[100005], t, x;

void cautbin (int left, int right) {
    //fout << "left = " << left << ", right = " << right << '\n';
    if (left == right) {
        if (t == 0) {
            if (v[left] != x) {
                fout << '-1 \n';
                return;
            }
            while (v[left] == x) left++;
            fout << left - 1 << '\n';
        }
        else if (t == 1) {
            while (v[right] <= x) right++;
            fout << right - 1 << '\n';
        }
        else {
            while (v[left] >= x) left--;
            fout << left + 1 << '\n';
        }
        return;
    }
    int div = (left+right) / 2;
    //if (x == v[div]) cautbin(div,div);
    if(x <= v[div]) cautbin(left,div);
    else cautbin(div+1,right);
}

int main()
{
    int n, m;

    fin >> n;

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

    fin >> m;

    for (int i=1; i <= m; i++) {
        fin >> t >> x;
        cautbin(1,n);
    }


    return 0;
}