#pragma region Template
#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
#define ll long long
#pragma endregion Template
int vect[100'005];

int binSrc(int size, int find) {
    int left = 0, right = size - 1;
    int pos = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (vect[mid] == find)
            pos = mid + 1, left = mid + 1;
        else if (vect[mid] < find)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return pos;
}

int lowerBound(int size, int find) {
    int left = 0, right = size - 1;
    int pos = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (vect[mid] >= find)
            pos = mid + 1, right = mid - 1;
        else if (vect[mid] < find)
            left = mid + 1;
    }
    return pos;
}

int upperBound(int size, int find) {
    int left = 0, right = size - 1;
    int pos = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (vect[mid] <= find)
            pos = mid + 1, left = mid + 1;
        else if (vect[mid] > find)
            right = mid - 1;
    }
    return pos;
}

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

    int n;      scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &vect[i]);
    int m;     scanf("%d", &m);
    while (m--) {
        int option, num;     scanf("%d%d", &option, &num);
        int ans;
        switch (option) {
            case 0:
                ans = binSrc(n, num);
                break;
            case 1:
                ans = upperBound(n, num);
                break;
            default:
                ans = lowerBound(n, num);
                break;
        };
        printf("%d\n", ans);
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}