#include <fstream>
using namespace std;

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

int arr[100000];

int main()
{
    int n, m, c, x, l, r, mij;
    fin >> n;
    for (int i=0; i<n; i++) fin >> arr[i];
    fin >> m;
    for (int i=1; i<=m; i++) {
        fin >> c >> x;
        if (c == 0 || c == 1) {
            l = 0, r = n;
            while (l < r) {
                mij = (l + r) / 2;
                if (arr[mij] > x) r = mij - 1;
                else l = mij;
            }
            if (c == 0 && arr[l] != x) fout << "-1\n";
            else fout << l + 1 << endl;
        }
        else {
            l = 0, r = n;
            while (l < r) {
                mij = (l + r) / 2;
                if (arr[mij] < x) l = mij + 1;
                else r = mij;
            }
            fout << l + 1 << endl;
        }
    }
}