/// Craciun Catalin
///  Cautbin
///   www.infoarena.ro/problema/cautbin
#include <fstream>
#include <iostream>

#define NMax 100005

using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

long V[NMax];
long n,m;

int main()
{
    f>>n;
    for (long i=1;i<=n;i++)
        f>>V[i];
    f>>m;
    for (long i=1;i<=m;i++)
    {
        long x,y;
        f>>x>>y;
        if (x==0)
        {
            long st=1, dr=n;
            long m;
            while (st<=dr)
            {
                m=(st+dr)/2;
                if (V[m]<=y)
                    st=m+1;
                else
                    dr=m-1;
            }

            if (V[m]>y)
                m--;
            if (V[m]==y)
                g<<m<<'\n';
            else
                g<<-1<<'\n';
        }
        else if (x==1)
        {
            long st=1, dr=n;
            long m;

            while (st<=dr)
            {
                m=(st+dr)/2;
                if (V[m]<=y)
                    st=m+1;
                else
                    dr=m-1;
            }

            while (V[m]>y)
                m--;

            g<<m<<'\n';
        }
        else if (x==2)
        {
            long st=1, dr=n;
            long m;

            while (st<=dr)
            {
                m=(st+dr)/2;
                if (V[m]>=y)
                    dr=m-1;
                else
                    st=m+1;
            }

            m=(st+dr)/2;

            while (V[m]<y)
                m++;

            g<<m<<'\n';
        }
    }
    f.close();

    return 0;
}