#include <bits/stdc++.h>
#define MAXSZ 100010

using namespace std;

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

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

    if (arr[hi] > x)
        hi--;
    return arr[hi] == x ? hi + 1 : -1;
}

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

    if (arr[hi] > x)
        hi--;
    return hi + 1;
}

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

    if (arr[hi] < x)
        hi--;
    return lo + 1;
}

int main() {
    int n, arr[MAXSZ];
    fin >> n;
    for (int i = 0; i < n; i++)
        fin >> arr[i];

    int m;
    fin >> m;
    for (int q = 0; q < m; q++) {
        int t, x;
        fin >> t >> x;
        switch (t) {
            case 0:
                fout << binarySearch(n, arr, x) << '\n';
                break;
            case 1:
                fout << lowerBound(n, arr, x) << '\n';
                break;
            case 2:
                fout << higherBound(n, arr, x) << '\n';
                break;
        }
    }
    return 0;
}