#include <iostream>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int mi, n, m, i, x, val, v[100001];
void Cautare(int x, int st, int dr)
{
    while ( st <= dr)
    {
        mi = ( st +dr )/2;
        if ( v[mi] == x )
            break;
        if ( v[mi] <= x )
            st = mi + 1;
        else dr = mi - 1;
    }
}
int main()
{   f >> n;
    for ( i=1; i<=n; i++)
        f >> v[i];
    f >> m;
    for ( i=1; i<=m; i++)
        {
            f >> val >> x;
            if ( val == 0 )
                {
                    Cautare(x,1,n);
                    if ( v[mi] == x )

                        {
                            while ( v[mi+1] == v[mi] )
                                mi++;
                            g << mi << '\n';
                        }
                    else
                        g << "-1" << '\n';
                }
            else if( val == 1 )
                {
                    Cautare(x,1,n);
                    if ( v[mi] == x)
                        while ( v[mi+1] <= v[mi] && mi < n )
                            mi++;
                    else if ( v[mi] > x )
                        mi--;
                    g << mi <<'\n';
                }
            else
                {
                    Cautare(x,1,n);
                    if ( v[mi] == x )
                        while ( v[mi-1] >= v[mi] && mi > 1 )
                            mi--;
                    else if ( v[mi] < x )
                        m++;
                    g << mi << '\n';
                }
        }
    return 0;
}