// programul raspunde la interogari prin cautari binare asupra unui sir ordonat

#include <bits/stdc++.h>

using namespace std;

int v[100001], n, m;

// tip0 -> ultima pozitie cu v[mid] == x
int caut0(int x) {
    int st = 0, dr = n - 1, rasp = -1;
    while (st <= dr) {
        int mid = (st + dr) / 2;
        if (v[mid] == x) {
            rasp = mid;
            st = mid + 1; // mai caut in dreapta
        } else if (v[mid] < x) {
            st = mid + 1;
        } else {
            dr = mid - 1;
        }
    }
    return (rasp == -1 ? -1 : rasp + 1); 
}

// tip1 -> ultima pozitie cu v[mid] <= x
int caut1(int x) {
    int st = 0, dr = n - 1, rasp = -1;
    while (st <= dr) {
        int mid = (st + dr) / 2;
        if (v[mid] <= x) {
            rasp = mid;
            st = mid + 1;
        } else {
            dr = mid - 1;
        }
    }
    return rasp + 1; // sigur exista
}

// tip2 -> prima pozitie cu v[mid] >= x
int caut2(int x) {
    int st = 0, dr = n - 1, rasp = -1;
    while (st <= dr) {
        int mid = (st + dr) / 2;
        if (v[mid] >= x) {
            rasp = mid;
            dr = mid - 1;
        } else {
            st = mid + 1;
        }
    }
    return rasp + 1; // sigur exista
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> v[i];

    cin >> m;

    for (int i = 0; i < m; i++) {
        int tip, x;
        cin >> tip >> x;

        // afisez tipurile
        if (tip == 0)
            cout << caut0(x) << "\n";
        else if (tip == 1)
            cout << caut1(x) << "\n";
        else
            cout << caut2(x) << "\n";
    }

    return 0;
}