#include <bits/stdc++.h>
#define maxN 100005
using namespace std;
int n, m, v[maxN];
void read()
{
    int i;
    freopen("cautbin.in", "r", stdin);
    scanf("%d", &n);
    for (i = 1; i <= n; ++ i)
        scanf("%d", &v[i]);
}
int bs1(int x)
{
    int i = 0, p = 1 << 16;
    while (p)
    {
        if (i + p <= n && v[i + p] <= x)
            i += p;
        p /= 2;
    }
    return i;
}
int bs2(int x)
{
    int i = 0, p = 1 << 16;
    while (p)
    {
        if (i + p <= n && v[i + p] < x)
            i += p;
        p /= 2;
    }
    return i;
}
void write()
{
    int x, y, i;
    freopen("cautbin.out", "w", stdout);
    scanf("%d", &m);
    while (m --)
    {
        scanf("%d %d", &x, &y);
        if (x == 0)
        {
            int p = bs1(y);
            if (v[p] == y)
                printf("%d\n", p);
            else
                printf("%d\n", -1);
        }
        else if (x == 1)
            printf("%d\n", bs1(y));
        else
            printf("%d\n",  bs2(y) + 1);
    }
}
int main()
{
    read();
    write();
    return 0;
}