#include <cstdio>

using namespace std;

int v[100001];
int n;

int caut_upper(int val)
{
    int st = 1, dr = n, mid;
    while(st < dr)
    {
        mid = (st + dr) / 2;
        if(v[mid] <= val) st = mid + 1;
        else dr = mid;
    }
    mid = (st + dr) / 2;
    if(v[mid] > val) mid--;
    return mid;
}

int caut_lower(int val)
{
    int st = 1, dr = n, mid;
    while(st < dr)
    {
        mid = (st + dr) / 2;
        if(v[mid] < val) st = mid + 1;
        else dr = mid;
    }
    mid = (st + dr) / 2;
    if(v[mid] < val) mid++;
    return mid;
}

int main()
{
    int ni, c, nr, r, i;
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
    scanf("%d", &n);
    for(i = 1; i <= n; i++)
        scanf("%d", &v[i]);
    scanf("%d", &ni);
    for(i = 0; i < ni; i++)
    {
        scanf("%d%d", &c, &nr);
        if(c == 0)
        {
            r = caut_upper(nr);
            if(v[r] != nr)
                printf("-1\n");
            else printf("%d\n", r);
        }
        else if(c == 1)
        {
            r = caut_upper(nr);
            printf("%d\n", r);
        }
        else
        {
            r = caut_lower(nr);
            printf("%d\n", r);
        }
    }
    return 0;
}