#include <iostream>
#include <fstream>
#include <vector>
#include <limits.h>

using namespace std;

int n, k;

int bsearch0(vector<int>& v, int x) {
    int l = 0, r = n - 1;
    int res = -1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (v[mid] < x) {
            l = mid + 1;
        } else if (v[mid] > x) {
            r = mid - 1;
        } else {
            res = mid + 1;
            l = mid + 1;
        }
    }
    return res;
}

int bsearch1(vector<int>& v, int x) {
    int l = 0, r = n - 1;
    int res = -1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (v[mid] <= x) {
            l = mid + 1;
            res = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return res;
}

int bsearch2(vector<int>& v, int x) {
    int l = 0, r = n - 1;
    int res = -1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (v[mid] >= x) {
            r = mid - 1;
            res = mid + 1;
        } else {
            l = mid + 1;
        }
    }
    return res;
}

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

    fin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
        fin >> v[i];
    }
    fin >> k;

    int t, x;
    for (int i = 0; i < k; ++i) {
        fin >> t >> x;
        if (!t)
            fout << bsearch0(v, x) << '\n';
        else if (t == 1)
            fout << bsearch1(v, x) << '\n';
        else
            fout << bsearch2(v, x) << '\n';
    }

    return 0;
}