#include<cstdio>
using namespace std;
int v[100007], n;
int cautbin(int c)
{
    int step = 1, start = 0;
    for(; step <= n; step <<= 1)
    {

    }
    for(; step; step >>= 1)
    {
        int index = step + start;
        if(n < index) continue;
        if(v[index] <= c) start = index;
    }
    return start;
}
int main()
{
    FILE* in = fopen("cautbin.in", "r");
    FILE* out = fopen("cautbin.out", "w");
    int m, x, t;
    fscanf(in, "%d", &n);
    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);
        if(t == 0)
        {
            int raspuns;
            if(v[cautbin(x)] < x) raspuns = -1;
            else raspuns = cautbin(x);
            fprintf(out, "%d\n", raspuns);
        }
        if(t == 1)
        {
            int raspuns = cautbin(x);
            fprintf(out, "%d\n", raspuns);
        }
        if(t == 2)
        {
            int raspuns = cautbin(x - 1) + 1;
            fprintf(out, "%d\n", raspuns);
        }
    }
}