#include<cstdio>
using namespace std;
int n, v[100007];
FILE* in = fopen("cautbin.in", "r");
FILE* out = fopen("cautbin.out", "w");
int cautbin(int a)
{
    int start = 0, step = 1;
    for(; step <= n; step <<= 1);
    for(; step; step >>= 1)
    {
        int index = start + step;
        if(n < index) continue;
        if(v[index] <= a) start = index;
    }
    return start;
}
int main()
{
    fscanf(in, "%d", &n);
    int x, t;
    int m;
    for(int i = 1; i <= n; ++i)
    {
        fscanf(in, "%d", &v[i]);
    }
    fscanf(in, "%d", &m);
    for(int i = 1; i <= m; ++i)
    {
        fscanf(in, "%d%d", &t, &x);
        int raspuns;
        if(t == 0)
        {
            if(v[cautbin(x)] != x) raspuns = -1;
            else raspuns = cautbin(x);
        }
        if(t == 1) raspuns = cautbin(x);
        if(t == 2) raspuns = cautbin(x - 1) + 1;
        fprintf(out, "%d\n", raspuns);
    }
}