// cautbin.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <fstream>
#include <iostream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int v[100001];
int bsearch0(int p, int u, int key) {
    int m;
    while (p <= u) {
        m = (p + u) / 2;
        if (v[m] <= key)
            p = m + 1;
        else
            u = m - 1;
    }
    m = (p + u) / 2;

    if (v[m] > key) m--;
    if (v[m] == key)
        return m;
    return -1;
}
int bsearch1(int p, int u, int key) {
    int m;
    while (key)
    {
        while (p <= u) {
            m = (p + u) / 2;
            if (v[m] <= key)
                p = m + 1;
            else
                u = m - 1;
        }
        m = (p + u) / 2;

        if (v[m] > key) m--;
        if (v[m] == key)
            return m;
        key--;
    } 
}

int bsearch2(int p, int u, int key) {
    int m;

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

    m = (p + u) / 2;
    if (v[m] < key)
        ++m;
    return m;
}
int main()
{
    int n, m, a, b, x;
    cin >> n;
    for (int i = 1; i<=n; i++) {
        cin >> v[i];
    }
    cin >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a >> b;
        if (a == 0) {
            cout << bsearch0(1, n, b) << '\n';
        }
        else if (a == 1) {
            cout << bsearch1(1, n, b) << '\n';
        }
        else if (a == 2) {
            cout << bsearch2(1, n, b) << '\n';
        }
    }
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file