#include <iostream>
#include <fstream>

using namespace std;

const int MAX_N = 100000;
int arr[MAX_N];

// **Binary search for last occurrence of `x` (0 x)**
int findLastOccurrence(int arr[], int n, int x) {
    int left = 0, right = n - 1, pos = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= x) { // Move right if arr[mid] == x
            if (arr[mid] == x) pos = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return pos;
}

// **Binary search for last element ≤ `x` (1 x)**
int findLastLessOrEqual(int arr[], int n, int x) {
    int left = 0, right = n - 1, pos = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= x) {
            pos = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return pos;
}

// **Binary search for first element ≥ `x` (2 x)**
int findFirstGreaterOrEqual(int arr[], int n, int x) {
    int left = 0, right = n - 1, pos = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] >= x) {
            pos = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return pos;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

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

    int N, M;
    fin >> N;
    
    // Read sorted array
    for (int i = 0; i < N; i++) {
        fin >> arr[i];
    }

    fin >> M;

    // Process each query
    for (int i = 0; i < M; i++) {
        int type, x;
        fin >> type >> x;
        
        if (type == 0)
            fout << findLastOccurrence(arr, N, x) << '\n';
        else if (type == 1)
            fout << findLastLessOrEqual(arr, N, x) << '\n';
        else if (type == 2)
            fout << findFirstGreaterOrEqual(arr, N, x) << '\n';
    }

    return 0;
}