#include <bits/stdc++.h>

using namespace std;
ifstream f ("cautbin.in");
ofstream g ("cautbin.out");
int i, n, v[100006], gasit, mij, pi, pj, x, m, intr;
void caut(int pi,int pj,int x)
{
    while( pi <= pj && gasit == 0)
    {
        mij = ( pi+pj ) /2;
        if( v[mij] == x)
            gasit = 1;
        else
        {
            if( v[mij] < x )
            {
                pi = mij + 1;
            }
            else
            {
                pj = mij-1;
            }
        }
    }
}
void intrebari()
{
    if( intr == 0 && gasit == 1)
    {
        while( v[mij] == v[mij+1] )
            mij++;
        g << mij << endl;
    }
    else if( intr == 0 && gasit == 0 )
        g << -1 << endl;
    else if( intr == 1 && gasit == 1)
    {
        while( v[mij] == v[mij+1] )
            mij++;
        g << mij <<endl;
    }
    else if( intr == 1 && gasit == 0)
    {
        caut(1,n,x-1);
        while(v[mij] > x)
                    mij--;
        while(v[mij + 1] == v[mij])
                      mij++;
        g << mij << endl;
    }
    else if( intr == 2 && gasit == 1)
    {
        while( v[mij] == v[mij-1] )
            mij--;
        g << mij << endl;
    }
    else
    {
        caut(1,n,x+1);
        while(v[mij] < x)
            mij++;
        while(v[mij-1] == v[mij])
            mij--;
        g << mij << endl;
    }
}
int main()
{
    f >> n;
    for( i = 1; i <= n; i++)
        f >> v[i];
    f >> m;
    while(m)
    {
        gasit = 0;
        f >> intr >> x;
        caut(1,n,x);
        intrebari();
        m--;
    }
    return 0;
}