#include <iostream>
#include <fstream>
using namespace std;
#define N 100010
	
int v[N];

int binsearch0(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;
    }
}

int binsearch1(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;
}

// Calculatorul face parte intreaga la nr
// nu le aproximeaza!!!!!
int binsearch2(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 m, type, x, n;

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

    fin >> n;

    for (int i = 1; i <= n; ++i) {
        int var;
        fin >> var;
        v[i] = var;
    }

    fin >> m;

    while (m--) {
        fin >> type >> x;
        if (type == 0) {
            fout << binsearch0(1, n, x) << "\n";
        }
        if (type == 1) {
            fout << binsearch1(1, n, x) << "\n";
        }
        if (type == 2) {
            fout << binsearch2(1, n, x) << "\n";
        }
    }

    return 0;
}