#include <bits/stdc++.h>
#define MAXN 100000

using namespace std;

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

int n, arr[MAXN], m;
void citire() {
    fin >> n;
    for (int i = 0; i < n; i++)
        fin >> arr[i];
    fin >> m;
}

int rezolvare() {
    int t, x;
    fin >> t >> x;
    if (t == 0) {
        int lo = 0, hi = n - 1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (arr[mid] <= x)
                lo = mid + 1;
            else
                hi = mid - 1;
        }

        return (arr[hi] == x ? hi : -1);
    } else if (t == 1) {
        int lo = 0, hi = n - 1, poz;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (arr[mid] <= x)
                lo = mid + 1, poz = mid;
            else
                hi = mid - 1;
        }
        return poz;
    }

    int lo = 0, hi = n - 1, poz;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (arr[mid] >= x)
            hi = mid - 1, poz = mid;
        else
            lo = mid + 1;
    }

    return poz;
}

int main() {
    citire();
    for (int i = 0; i < m; i++)
        fout << rezolvare() + 1 << '\n';
    return 0;
}