// Infoarena - Cautare Binara
#include <iostream>
#include <fstream>
#include <vector>

const int INF = 0x3f3f3f3f;

// cea mai mare pozitie pe care se afla un element cu valoarea x sau -1 daca aceasta valoare nu se gaseste in sir
int binarySearch0(std::vector <int>& arr, int value) 
{
    int left = 0;
    int right = (int)arr.size() - 1;
    int ans = -2;           // -2 pt. ca daca nr. nu se gaseste in vector, pozitia va fi -2 + 1 = -1, cum se cere
    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == value) {
            ans = mid;
            left = mid + 1;
        }
        else if (arr[mid] < value) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }

    return ans;
}

// cea mai mare pozitie pe care se afla un element cu valoarea mai mica sau egala cu x in sir. Se garanteaza ca cel mai mic numar al sirului este mai mic sau egal decat x
int binarySearch1(std::vector<int>& arr, int value)
{
    int left = 0;
    int right = (int)arr.size() - 1;
    int ans = 0;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == value) {
            ans = mid;
            left = mid + 1;
        }
        else if (arr[mid] < value) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }

    if (arr[left] > value) {
        ans = left - 1;
    }
    else {
        ans = left;
    }
    return ans;
}

// cea mai mica pozitie pe care se afla un element cu valoarea mai mare sau egala cu x in sir. Se garanteaza ca cel mai mare numar din sir este mai mare sau egal decat x
int binarySearch2(std::vector<int>& arr, int value)
{
    int left = 0;
    int right = (int)arr.size() - 1;
    int ans = right;

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == value) {
            ans = mid;
            right = mid - 1;
        }
        else if (arr[mid] < value) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }

    if (arr[left] < value) {
        ans = left + 1;
    }
    else {
        ans = left;
    }
    return ans;
}

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

    int n;
    fin >> n;

    std::vector <int> arr(n);
    for (int i = 0; i < n; i++) {
        fin >> arr[i];
    }

    int m;
    fin >> m;
    while (m--) {
        int query, value;
        fin >> query >> value;
        switch (query) {
            case 0:
                fout << binarySearch0(arr, value) + 1 << '\n';
                break;
            case 1:
                fout << binarySearch1(arr, value) + 1 << '\n';
                break;
            case 2:
                fout << binarySearch2(arr, value) + 1 << '\n';
                break;
        }
    }

    return 0;
}