#include <cstdio>
#include <algorithm>

using namespace std;

int i, t, x, n, m, val, a[100005];

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]);
    scanf("%d", &m);
    while(m--)
    {
        scanf("%d%d", &t, &x);
        if(!t)
        {
            val=upper_bound(a+1, a+n+1, x)-a-1;
            if(a[val]==x)
                printf("%d\n", val);
            else
                printf("-1\n");
        }
        else if(t==1)
        {
            val=lower_bound(a+1, a+n+1, x+1)-a-1;
            printf("%d\n", val);
        }
        else
        {
            val=upper_bound(a+1, a+n+1, x-1)-a;
            printf("%d\n", val);
        }
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}