// Programul raspunde la interogari prin cautari binare asupra unui sir ordonat (indexare 1-based)

#include <bits/stdc++.h>
using namespace std;

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

int v[100010];
int n, m;

// TIP 0: ultima pozitie unde v[mid] == key sau -1
int bsearch0(int p, int u, int key) {
    int rasp = -1, mid;

    while (p <= u) {
        mid = p + (u - p) / 2;
        if (v[mid] == key) {
            rasp = mid;
            p = mid + 1;   // cautam mai la dreapta
        } else if (v[mid] < key) {
            p = mid + 1;
        } else {
            u = mid - 1;
        }
    }
    return rasp; // -1 dacă nu există
}

// TIP 1: ultima pozitie unde v[mid] <= key (exista garantat)
int bsearch1(int p, int u, int key) {
    int rasp = p, mid;

    while (p <= u) {
        mid = p + (u - p) / 2;
        if (v[mid] <= key) {
            rasp = mid;
            p = mid + 1;
        } else {
            u = mid - 1;
        }
    }
    return rasp;
}

// TIP 2: prima pozitie unde v[mid] >= key (exista garantat)
int bsearch2(int p, int u, int key) {
    int rasp = u, mid;

    while (p <= u) {
        mid = p + (u - p) / 2;
        if (v[mid] >= key) {
            rasp = mid;
            u = mid - 1;
        } else {
            p = mid + 1;
        }
    }
    return rasp;
}

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

    cin >> m;
    while (m--) {
        int tip, val;
        cin >> tip >> val;

        if (tip == 0)
            cout << bsearch0(1, n, val) << "\n";
        else if (tip == 1)
            cout << bsearch1(1, n, val) << "\n";
        else
            cout << bsearch2(1, n, val) << "\n";
    }

    return 0;
}