#include <fstream>
#include <iostream>

using namespace std;

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

int v[100001],mid,n;


void cautbin(int x) {
    int st = 1, dr = n;
    while (st <= dr) {
        mid = st + (dr - st) / 2;
        if (v[mid] == x)
            break;
        else if (v[mid] > x)
            dr = mid - 1;
        else
            st = mid + 1;
    }
}

int main() {

    in >> n;

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


    int m, t, x;
    in >> m;

    for (int i = 1; i <= m; i++) {
        in >> t >> x;
        if (t == 0) {
            cautbin(x);

            if (v[mid] != x)
                out << -1 << '\n';
            else {
                while(v[mid+1]==v[mid])
                    mid++;
                out << mid << '\n';
            }

        }
        else if (t == 1) {
            if(v[mid] != x)
                out << mid-1 << '\n';
            else {
                while(v[mid+1]==v[mid])
                    mid++;
                out << mid << '\n';
            }

        }
        else {
            if(v[mid] != x)
                out << mid << '\n';
            else {
                while(v[mid-1]==v[mid])
                    mid--;
                out << mid << '\n';
            }
        }
    }

    return 0;
}