#include <cstdio>
#include <algorithm>
#define Nmax 100002

using namespace std;
int n, m, v[Nmax], pas;
int bsearch(int x)
{
    int i = 0;
    pas = 1 << 16;
    while(pas != 0)
    {
        if(i + pas <= n && v[i + pas] <= x)
            i += pas;
        pas /= 2;
    }
    return i;
}
int searchb(int x)
{
    int i = 0;
    pas = 1 << 16;
    while(pas != 0)
    {
        if(i + pas <= n && v[i + pas] < x)
            i += pas;
        pas /= 2;
    }
    return i;
}
int main()
{
    int i, pas, x, t;
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
    scanf("%d", &n);
    for(i = 1; i <= n; ++ i)
        scanf("%d", &v[i]);
    scanf("%d", &m);
    while(m --)
    {
        scanf("%d %d", &t, &x);
        if(t == 0 || t == 1)
        {
            i = bsearch(x);
            if(t == 0)
            {
                if(v[i] == x) printf("%d\n", i);
                else printf("-1\n");
            }
            else printf("%d\n", i);
        }
        else
        {
            i = searchb(x);
            printf("%d\n", i + 1);
        }
    }
    return 0;
}