#include <stdio.h>

unsigned int a[100001], N;

int main()
{
    unsigned int i, position, M, op, value, l, r, middle;
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);

    scanf("%u", &N);
    for(i = 1; i <= N; i++)
        scanf("%u", &a[i]);
    scanf("%u", &M);
    for(; M; --M)
    {
        scanf("%u %u", &op, &value);
        l = 1; 
        r = N;
        while(l <= r)
        {
            middle = (r - l) / 2 + l;
            if(op < 2 && a[middle] <= value)
            {
                position = middle;
                l = middle + 1;
            }
            else if(op < 2)
                r = middle - 1;
            else if(op == 2 && value <= a[middle])
            {
                position = middle;
                r = middle - 1;
            }
            else
                l = middle + 1;
        }

        if(op == 0 && a[position] != value)
            printf("-1\n");
        else
            printf("%u\n", position);
    }

    return 0;
}