#include<cstdio>
#include<algorithm>
#include<windows.h>
using namespace std;
int n, v[100007];
int cautbin(int a)
{
    int start = 0, pas = 1;
    for(; pas <= n; pas <<= 1);
    for(; pas; pas >>= 1)
    {
        int ind = start + pas;
        if(n < ind) continue;
        if(v[ind] <= a) start = ind;
    }
    return start;
}
int main()
{
    FILE* in = fopen("cautbin.in", "r"); ///probleme
    FILE* out = fopen("cautbin.out", "w");
    int m;
    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)
    {
        int a, x;
        int raspuns;
        fscanf(in, "%d%d", &a, &x);
        if(a == 0)
        {
            raspuns = cautbin(x);
            if(v[raspuns] != x) raspuns = -1;
        }
        if(a == 1)
        {
            raspuns = cautbin(x);
        }
        if(a == 2)
        {
            raspuns = cautbin(x - 1) + 1;
        }
        fprintf(out, "%d\n", raspuns);
    }
}