#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn=100100;

int n, a[maxn], i, q, x, y, k;

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

    scanf("%d", &n);
    for(i=1; i<=n; ++i) scanf("%d", a+i);

    for(scanf("%d", &q); q; --q)
    {
        scanf("%d %d", &y, &x);

        if(y==0)
        {
            k= upper_bound(a+1, a+n+1, x) - a - 1;
            if(a[k]==x) printf("%d\n", k);
            else printf("-1\n");
        }
        else if(y==1)
        {
            k= lower_bound(a+1, a+n+1, x+1) - a - 1;
            printf("%d\n", k);
        }
        else
        {
            k= upper_bound(a+1, a+n+1, x-1) - a;
            printf("%d\n", k);
        }
    }
}