#include <fstream>

using namespace std;

int binarySearchA(int left, int right, int arr[], int x)
{
    int middle, cLeft = left;
    while (right - left > 1)
    {
        middle = left + (right - left) / 2;
        if (arr[middle] <= x)
            left = middle;
        else
            right = middle;
    }

    if (left == cLeft || arr[left] != x)
        return -1;
    return left + 1;
}

int binarySearchB(int left, int right, int arr[], int x)
{
    int middle;
    while (right - left > 1)
    {
        middle = left + (right - left) / 2;
        if (arr[middle] <= x)
            left = middle;
        else
            right = middle;
    }

    return left + 1;
}

int binarySearchC(int left, int right, int arr[], int x)
{
    int middle;
    while (right - left > 1)
    {
        middle = left + (right - left) / 2;
        if (arr[middle] >= x)
            right = middle;
        else
            left = middle;
    }

    return right + 1;
}

int main()
{
    int N, M, i;
    ifstream f("cautbin.in");
    f >> N;
    int a[N];
    for (i = 0; i < N; i++)
        f >> a[i];
    f >> M;

    int x, type;
    ofstream g("cautbin.out");
    for (i = 0; i < M; i++)
    {
        f >> type >> x;
        if (type == 0)
            g << binarySearchA(-1, N, a, x);
        else if (type == 1)
            g << binarySearchB(-1, N, a, x);
        else if (type == 2)
            g << binarySearchC(-1, N, a, x);
        g << '\n';
    }

    f.close();
    g.close();
    return 0;
}