#include <fstream>

using namespace std;
int step,N,val,V[100000],i,t,j,type,cop;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int main()
{
    f>>N;
    for(i=1; i<=N; i++)
        f>>V[i];
    f>>t;
    for (step = 1; step < N; step <<= 1);
    cop=step;
    for(j=1; j<=t; j++)
    {
        f>>type>>val;
        step=cop;
        if(!type)
        {
            for (i = 0; step; step >>=1)
                if (i + step <= N && V[i + step] <= val)
                    i += step;
            if(!step)
            g<<i<<'\n';
            else g<<-1<<'\n';
        }
        else if(type==1)
        {
            for (i = 0; step; step >>= 1)
                if (i + step <= N && V[i + step] <= val)
                    i += step;
            g<<i<<'\n';
        }
        else if(type==2)
        {
            for (i = N; step; step >>= 1)
                if (i - step >= 1 && V[i - step] >=val)
                    i -= step;
            g<<i<<'\n';
        }
    }
    return 0;
}