#include <iostream>
#include <fstream>
#include <cstdio>

#define pb push_back

using namespace std;

int n[100000];

int uppB(int* n, int len, int key) {
    int low = 0, high = len - 1;
    while (low < high) {
        int mid = low + (1 + high - low) / 2;
        if (n[mid] == key) low = mid;
        else if (n[mid] < key) low = 1 + mid;
        else high = mid - 1;
    }
    return key == n[low] ? 1 + low : -1;
}

int uppLB(int* n, int len, int key) {
    int low = 0, high = len - 1;
    while (low < high) {
        int mid = low + (1 + high - low) / 2;
        if (n[mid] <= key) low = mid;
        else high = mid - 1;
    }
    return 1 + low;
}

int lowB(int* n, int len, int key) {
    int low = 0, high = len - 1;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (key <= n[mid]) high = mid;
        else low = 1 + mid;
    }
    return 1 + low;
}

int main() {
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);

    int N;
    scanf("%d", &N);
    for (int it = 0; it < N; ++it) {
        scanf("%d", &n[it]);
    }
    int M, type, key;
    scanf("%d", &M);
    for (int it = 0; it < M; ++it) {
        scanf("%d%d", &type, &key);
        switch(type) {
            case 0: {
                cout << uppB(n, N, key) << endl;
                break;
            }
            case 1: {
                cout << uppLB(n, N, key) << endl;
                break;
            }
            case 2: {
                cout << lowB(n, N, key) << endl;
                break;
            }
        }
    }

    return 0;
}