#include <fstream>

using namespace std;
ifstream f1("cautbin.in");
ofstream f2("cautbin.out");

int n, a[100010],i, m;

int cautare1(int st, int dr, int val)
{
    if (dr-st <= 1)
        {
            if ( a[dr] == val ) return dr;
            else { if ( a[st] == val )
                    return st;
                   else return -1; }
        }

    int m= (st+dr)/2;

    if ( val >= a[m] ) return cautare1(m, dr,val);
        else return cautare1(st, m-1,val);
}

int cautare2(int st, int dr, int val)
{
    if (dr-st <= 1)
        {
            if ( a[dr] <= val ) return dr;
            else if ( a[st] <= val )
                    return st;
        }

    int m= (st+dr)/2;

    if ( a[m] <= val ) return cautare2(m, dr,val);
        else return cautare2(st, m-1,val);
}

int cautare3(int st, int dr, int val)
{
    if (dr-st <= 1)
        {
            if ( a[st] >= val ) return st;
            else if ( a[dr] >= val )
                    return dr;
        }

    int m= (st+dr)/2;

    if ( a[m] >= val ) return cautare3(st, m,val);
        else return cautare3(m+1, dr,val);
}

int main()
{
    f1>>n;
    for (i= 1; i<=n; i++)
        f1>>a[i];

    f1>>m;
    for (i= 1; i<=m; i++)
    {
        int cod,x, rez;
        f1>>cod>>x;
        if ( cod == 0 )
            rez= cautare1(1,n,x);
            else if ( cod == 1 )
                    rez= cautare2(1,n,x);
                 else
                    rez= cautare3(1,n,x);

        f2<<rez<<"\n";
    }

    f2.close();
    return 0;
}