#include <iostream>
#include <fstream>

using namespace std;

int v[100000];

int cautare_binara(int s, int d, int info) {
    int mid;
    while (s <= d) {
        mid = (s + d) / 2;
        if (v[mid] <= info)
            s = mid + 1;
        else
            d = mid - 1;
    }
    mid = (s + d) / 2;
    if (v[mid] > info)
        mid--;
    if (v[mid] == info)
        return mid;
    return -1;

}

int cautare_binara1(int s, int d, int info) {
    int mid;
    while (s < d) {
        mid = (s + d) / 2;
        if (v[mid] <= info)
            s = mid + 1;
        else
            d = mid;
    }
    mid = (s + d) / 2;
    if (v[mid] > info)
        mid--;
    return mid;
}

int cautare_binara2(int s, int d, int info) {
    int mid;
    while (s < d) {
        mid = (s + d) / 2;
        if (v[mid] < info)
            s = mid + 1;
        else
            d = mid;
    }
    mid = (s + d) / 2;
    if (v[mid] < info)
        mid++;
    return mid;
}

int main() {
    int n, mid, tip, info;
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    f >> n;
    for (int i = 1; i <= n; i++)
        f >> v[i];
    f >> mid;
    while (mid) {
        f >> tip >> info;
        if(tip==0) g << cautare_binara(1,n,info) << "\n";
        if(tip == 1)  g << cautare_binara1(1,n,info) << "\n";
        if(tip == 2) g << cautare_binara2(1,n,info)<< "\n";
        mid--;
    }
    return 0;
}