#include <iostream>
#include <fstream>

#define MAX_SIZE 100001

int main() {
    std::ifstream input("cautbin.in");
    std::ofstream output("cautbin.out");

    int n, m;
    unsigned int a[MAX_SIZE] = {0};
    input >> n;

    for (int i = 1; i <= n; ++i) input >> a[i];


    input >> m;
    while (m--) {
        int type, x;
        input >> type >> x;
        if (type == 0) {
            int pos = -1, left = 1, right = n;
            while (left <= right) {
                int mid = (left + right) / 2;

                if (a[mid] == x) {
                    pos = mid;
                    left = mid + 1;
                } else if (a[mid] < x) {
                    left = mid + 1;
                } else right = mid - 1;

            }
            output << pos << '\n';
        } else if (type == 1) {
            int pos = -1, left = 1, right = n;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (a[mid] <= x) {
                    pos = mid;
                    left = mid + 1;
                } else right = mid - 1;
            }
            output << pos << '\n';
        } else {
            int pos = -1, left = 1, right = n;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (a[mid] >= x) {
                    pos = mid;
                    right = mid - 1;
                } else left = mid + 1;
            }
            output << pos << '\n';
        }
    }
    return 0;
}