#include <fstream>

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