#include <iostream>
#include <cstdio>

using namespace std;

#define maxN 100005

int x[maxN], N, M;

int lowerBoundBinarySearch(int nr)
{
    int lo = -1;
    int hi = N + 1;
    int mid;

    while(hi - lo > 1)
    {
        mid = (lo + hi) / 2;

        if(x[mid] >= nr)
            hi = mid;

        else lo = mid;
    }

    return hi;
}

int upperBoundBinarySearch(int nr)
{
    int lo = -1;
    int hi = N + 1;
    int mid;

    while(hi - lo > 1)
    {
        mid = (lo + hi) / 2;

        if(x[mid] <= nr)
            lo = mid;

        else hi = mid;
    }

    return lo;
}

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

    int queryType, number;

    scanf("%d" , &N);
    for(int i = 1; i <= N; ++i)
        scanf("%d", &x[i]);

    scanf("%d", &M);
    for(int i = 0; i < M; ++i)
    {
        scanf("%d %d", &queryType, &number);

        if(queryType == 0)
        {
            int sol = upperBoundBinarySearch(number);

            if(sol == -1 || x[sol] != number)
                printf("%d\n", -1);

            else printf("%d\n", sol);
        }

        else if(queryType == 1)
        {
            int sol = upperBoundBinarySearch(number);

            printf("%d\n", sol);
        }

        else
        {
            int sol = lowerBoundBinarySearch(number);

            printf("%d\n", sol);
        }
    }

    return 0;
}