#include <cstdio>

using namespace std;

int v[100001];

int main()
{
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
    int n, m, x, st, dr, mij, poz;
    short var;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", &v[i]);
    scanf("%d", &m);
    while(m--)
    {
        scanf("%hd %d", &var, &x);
        st = 1; dr = n;
        poz = -1;
        if(!var)
        {
            while(st <= dr)
            {
                mij = st + (dr - st) / 2;
                if(v[mij] == x)
                {
                    poz = mij;
                    st = mij + 1;
                }
                else if(x > v[mij]) st = mij + 1;
                else dr = mij - 1;
            }
            printf("%d\n", poz);
        }
        else if(var == 1)
        {
            while(st <= dr)
            {
                mij = st + (dr - st) / 2;
                if(v[mij] <= x)
                {
                    poz = mij;
                    st = mij + 1;
                }
                else if(v[mij] > x) dr = mij - 1;
            }
            printf("%d\n", poz);
        }
        else
        {
            while(st <= dr)
            {
                mij = st + (dr - st) / 2;
                if(v[mij] >= x)
                {
                    poz = mij;
                    dr = mij - 1;
                }
                else if(v[mij] < x) st = mij + 1;
            }
            printf("%d\n", poz);
        }
    }
    return 0;
}