#include <iostream>
#include <fstream>

using namespace std;
int v[100001];

int cautbin0(int left, int right, int val){
    int mid;

    while (left <= right){
        mid = (left + right) / 2;
        if (v[mid] <= val){
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    mid = (left + right) / 2;

    if (v[mid] > val) mid--;
    if (v[mid] == val){
        return mid;
    }
    return -1;
}

int cautbin1(int left, int right, int val){
    int mid;

    while (left < right){
        mid = (left + right) / 2;
        if (v[mid] <= val){
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    mid = (left + right) / 2;

    if (v[mid] > val) mid--;
    return mid;
}

int cautbin2(int left, int right, int val){
    int mid;

    while (left < right){
        mid = (left + right) / 2;
        if (v[mid] < val){
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    mid = (left + right) / 2;

    if (v[mid] < val) mid++;
    return mid;
}

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

    int nr, n, i, val, c;

    fin >> nr;
    for (i = 1; i <= nr; i++){
        fin >> v[i];
    }
    fin >> n;
    for (i = 1; i <= n; i++){
        fin >> c >> val;
        if (c == 0){
            fout << cautbin0(1, nr, val) << "\n";
        }
        if (c == 1){
            fout << cautbin1(1, nr, val) << "\n";
        }
        if (c == 2){
            fout << cautbin2(1, nr, val) << "\n";
        }
    }
    return 0;
}