#include <fstream>
using namespace std;
ifstream in ("cautbin.in");
ofstream out("cautbin.out");
int v[100001];

int caut0(int st, int dr, int x)
{
    if (st == dr)
        if (x == v[st]) return st;
        else return -1;
    int m = (st + dr + 1)/2;
    if (x >= v[m]) return caut0(m, dr, x);
    return caut0(st, m-1, x);
}

int caut1(int st, int dr, int x)
{
    if (st == dr)
        return st;
    int m = (st + dr + 1)/2;
    if (x>=v[m]) return caut1 (m, dr, x);
    return caut1 (st, m-1, x);
}

int caut2 (int st, int dr, int x)
{
    if (st == dr)
        return st;
    int m = (st + dr)/2;
    if (x<=v[m]) return caut2 (st, m, x);
    return caut2 (m+1, dr, x);
}

int main ()
{
    int n, m, i, x, tip, max;
    in>>n;
    for (i=1; i<=n; i++)
    {
        in >> v[i];
    }
    in >> m;
    for (i=1; i<=m; i++)
    {
        in >> tip >> x;
        if ( tip == 0 )
        {
            max= caut0(1, n, x);
            out<< max << "\n";
        }
        if ( tip == 1 )
        {
            max= caut1(1, n, x);
            out<< max << "\n";
        }
        if(tip == 2)
        {
            max= caut2(1, n, x);
            out<< max << "\n";
        }
    }
    return 0;
}