#include <iostream>
#include <fstream>

using namespace std;

int cautare0(int v[], int n, int x) {
    int st = 1, dr = n, m;
    while (st <= dr) {
        m = (st + dr) / 2;
        if (x >= v[m])
            st = m + 1;
        else
            dr = m - 1;
    }
    m = (st + dr) / 2;
    if (x < v[m]) m--;
    if (x == v[m]) return m;
    return -1;
}

int cautare1(int v[], int n, int x) {
    int st = 1, dr = n, m;
    while (st < dr) {
        m = (st + dr) / 2;
        if (x >= v[m])
            st = m + 1;
        else
            dr = m;
    }
    m = (st + dr) / 2;
    if (x < v[m])
        m--;
    return m;
}

int cautare2(int v[], int n, int x) {
    int st = 1, dr = n, m;
    while (st < dr) {
        m = (st + dr) / 2;
        if (x > v[m])
            st = m + 1;
        else
            dr = m;
    }

    m = (st + dr) / 2;
    if (x > v[m])
        m++;
    return m;
}

int main() {
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    int v[100001], n, m, i, k, x;
    fin >> n;
    for (i = 1; i <= n; ++i)
        fin >> v[i];
    fin >> m;
    for (i = 1; i <= m; ++i) {
        fin >> k >> x;
        if(k == 0)
            fout << cautare0(v, n, x) << "\n";
        else if(k == 1)
            fout << cautare1(v, n, x) << "\n";
        else
            fout << cautare2(v, n, x) << "\n";
    }
}