#include <iostream>
#include <fstream>
using namespace std;
int a,n,m,x,j,limS, limD ,v[100001],mij;
int main()
{
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    f>>n;
    for (int i=1;i<=n;i++)
        f>>v[i];
    f>>m;
    for (int i=1;i<=m;i++)
    {
        f>>a>>x;
        limS=0;//limita stanga;
        limD=n+1;//limita dreapta;
        if (a==0)
        {
            while (limD-limS!=1)
            {
                mij=limS+(limD-limS)/2;
                if (x>=v[mij]) limS=mij;
                    else limD=mij;
            }
            mij=limS+(limD-limS)/2;
            if (v[mij]==x) g<<mij<<'\n';
                    else g<<"-1"<<'\n';
        }
        if (a==1)
        {
            while (limD-limS!=1)
            {
                mij=limS+(limD-limS)/2;
                if (x>=v[mij]) limS=mij;
                    else limD=mij;
            }
            mij=limS+(limD-limS)/2;
            g<<mij<<'\n';
        }
        if (a==2)
        {
            while (limD-limS!=1)
            {
                mij=limS+(limD-limS)/2;
                if (x<=v[mij]) limD=mij;
                    else limS=mij;
            }
            //mij=limS+(limD-limS)/2;
            g<<limD<<'\n';
        }
    }

    return 0;
}