#include <iostream>
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 < n)
                                mi++;
                            g << mi;
                        }
                    else
                        g << "-1";
                }
            else if( val == 1 )
                {
                    Cautare(x,1,n);
                    while ( v[mi+1] <= x && mi < n)
                        mi++;
                    g << mi;
                }
            else
                {
                    Cautare(x,1,n);
                    while ( v[mi-1] >= x && 1<mi)
                        mi--;
                    g << mi;
                }
        }
    return 0;
}