#include <stdio.h>

unsigned int a[100005], N;

int main()
{
    unsigned int i, position, lgN, M, op, value;
    FILE *in, *out;
    in = fopen("cautbin.in", "r");
    out = fopen("cautbin.out", "w");

    fscanf(in, "%u", &N);
    for(i = 1; i <= N; i++)
        fscanf(in, "%u", &a[i]);

    for(lgN = 1; (lgN << 1) <= N; lgN <<= 1);
    
    fscanf(in, "%u", &M);
    for(; M; --M)
    {
        fscanf(in, "%u %u", &op, &value);
        if(op < 2)
        {    
            for(i = lgN, position = 0; i; i >>= 1)
                if(position + i <= N && a[position + i] <= value)
                    position += i;
        }
        else
        {    
            for(i = lgN, position = N; i; i >>= 1)
            {
                if(position > i && value <= a[position - i])
                    position -= i;
            }
        }

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

    fclose(in);
    fclose(out);
    return 0;
}