#include <bits/stdc++.h>
#define infile "cautbin.in"
#define outfile "cautbin.out"
#define NMAX 100005

using namespace std;

int n, m, op, x, v[NMAX];

int bin_search0(int l, int r, int k)
{
    int m;

    while (l <= r)
    {
        m = (l + r) / 2;
        if (v[m] <= k)
        {
            l = m + 1;
        }
        else
        {
            r = m - 1;
        }
    }

    m = (l + r) / 2;
    if (v[m] > k) --m;
    if (v[m] == k)
        return m;
    return -1;
}

int bin_search1(int l, int r, int k)
{
    int m;

    while (l < r)
    {
        m = (l + r) / 2;
        if (v[m] < k)
        {
            l = m + 1;
        }
        else
        {
            r = m;
        }
    }

    m = (l + r) / 2;
    if (v[m] < k) ++m;

    return m;
}

int bin_search2(int l, int r, int k)
{
    int m;

    while (l < r)
    {
        m = (l + r) / 2;
        if (v[m] <= k)
        {
            l = m + 1;
        }
        else
        {
            r = m;
        }
    }

    m = (l + r) / 2;
    if (v[m] > k) --m;

    return m;
}

int main()
{
    freopen(infile, "r", stdin);
    freopen(outfile, "w", stdout);

    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &v[i]);
    }

    scanf("%d", &m);
    for (int i = 0; i < m; ++i)
    {
        scanf("%d %d", &op, &x);
        switch (op)
        {
        case 0:
            printf("%d\n", bin_search0(1, n, x));
            break;
        case 1:
            printf("%d\n", bin_search2(1, n, x));
            break;
        case 2:
            printf("%d\n", bin_search1(1, n, x));
            break;
        }
    }

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