#include <fstream>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n,i,v[100005],m,p,u,ok,q,x,mij,poz;
int main()
{
    fin >>n;
    for (i=1;i<=n;i++)
    {
        fin >>v[i];
    }
    fin >>m;
    for (i=1;i<=m;i++)
    {
        fin >>q>>x;
        if (q==0)
        {
            p=1;
            u=n;
            poz=-1;
            while (p<=u)
            {
                mij=(p+u)/2;
                if (v[mij]==x) {p=mij+1;poz=mij;}
                else if (v[mij]<x) p=mij+1;
                else u=mij-1;
            }
            fout <<poz<<'\n';
        }
        else if (q==1)
        {
                p=1;
                u=n;
                while (p<=u)
                {
                    mij=(p+u)/2;
                    if (v[mij]<=x) {poz=mij;p=mij+1;}
                    else u=mij-1;
                }
                fout <<poz<<'\n';

        }
        else
        {
            p=1;
            u=n;
            while (p<=u)
            {
                mij=(u+p)/2;
                if (v[mij]>=x) {poz=mij;u=mij-1;}
                else p=mij+1;
            }
            fout <<poz<<'\n';
        }
    }
    return 0;
}