#include <cstdio>

#define LGMAX 100001

using namespace std;

FILE *inFile = fopen ("cautbin.in", "r");
FILE *outFile = fopen ("cautbin.out", "w");

int n;
int a[LGMAX];

void read()
{
    fscanf (inFile, "%d\n", &n);

    for (int i = 1; i <= n; ++i)
        fscanf (inFile, "%d ", &a[i]);
}

int search0(int x)
{
    int left = 1;
    int right = n;

    while (left <= right)
    {
        int mid = left + ((right - left) >> 1);

        if (a[mid] == x)
        {
            left = mid + 1;

            if (mid == n || a[mid + 1] > x)
                return mid;
        }
        else
            right = mid - 1;
    }

    return -1;
}

int search1(int x)
{
    int left = 1;
    int right = n;

    while (left <= right)
    {
        int mid = left + ((right - left) >> 1);

        if (a[mid] <= x)
        {
            left = mid + 1;

            if (mid == n || a[mid + 1] > x)
                return mid;
        }
        else
            right = mid - 1;
    }

    return -1;
}

int search2(int x)
{
    int left = 1;
    int right = n;

    while (left <= right)
    {
        int mid = left + ((right - left) >> 1);

        if (a[mid] >= x)
        {
            right = mid - 1;

            if (mid == 1 || a[mid - 1] < x)
                return mid;
        }
        else
            left = mid + 1;
    }

    return -1;
}

int main()
{
    read();

    int m;
    int c;
    int x;

    fscanf (inFile, "%d\n", &m);
    while (m--)
    {
        fscanf (inFile, "%d %d\n", &c, &x);

        if (c == 0)
            fprintf (outFile, "%d\n", search0(x));
        else
            if (c == 1)
                fprintf (outFile, "%d\n", search1(x));
            else
                fprintf (outFile, "%d\n", search2(x));
    }
    return 0;
}