#include<cstdio>
#include<algorithm>
using namespace std;

const int NMAX = 100009;
int n, m, type, key, v[NMAX];

int main()
{
    freopen("cautbin.in" , "rt" , stdin); freopen("cautbin.out", "wt", stdout);

    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", &v[i]);
    scanf("%d", &m);
    int x;
    while(m--)
    {
        scanf("%d%d", &type, &key);
        if(!type)
        {
            x = upper_bound(v + 1, v + n + 1, key) - v - 1;
            if(x <= n && x >= 1 && v[x] == key) printf("%d\n", x);
            else printf("-1\n");
        }
        else
        if(type == 1)
        {
            x = lower_bound(v + 1, v + n + 1, key + 1) - v;
            printf("%d\n", x - 1);
        }
        else
        {
            x = upper_bound(v + 1, v + n + 1, key - 1) - v - 1;
            printf("%d\n", x + 1);
        }
    }
}