#include <iostream>
#include <fstream>
using namespace std;
int n, m, a[500001], tipCaut, x;

int cautbin0(int x) {
    int s =1, d = n, m;
    while (s <= d){
        m = s+ (d-s) / 2;
        if (x >= a[m])
            s = m+1;
        else
            d = m-1;
    }
    m = s+ (d-s) / 2;
    if (x < a[m]) m--;
    if (x == a[m]) return m;
    return -1;
}

int cautbin1(int x) {
    int s = 1, d = n, m;
    while (s < d) {
        m = s+ (d-s) / 2;
        if (x >= a[m])
            s = m + 1;
        else
            d = m;
    }
    m = s+ (d-s) / 2;
    if (x < a[m])
        m--;
    return m;
}

int cautbin2(int x) {
    int s=1, d = n, m;
    while (s < d) {
        m = s+ (d-s) / 2;
        if (x > a[m])
            s = m + 1;
        else
            d = m;
    }

    m = s+ (d-s) / 2;
    if (x > a[m])
        m++;
    return m;
}


int main()
{ifstream in ("cautbin.in");
ofstream out ("cautbin.out");
in >> n;
for (int i = 1 ; i <= n ; ++i)
    in >> a[i];
in >> m;
for (int i = 1 ; i <= m ; ++i){
    in >> tipCaut >> x;
    if (tipCaut == 0)
        out << cautbin0(x) << '\n';
    else if (tipCaut == 1)
        out << cautbin1(x) << '\n';
    else out << cautbin2(x) << '\n';
}
in.close();
out.close();

}