#include <fstream>
using namespace std;

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

int n,i,x,y,m, a[100002];

int bs0(int ls, int ld, int x)
{
    int m,poz;
    poz=-1;
    while (ls<=ld)
        {
            m=(ls+ld)/2;
            if (a[m]==x){poz=m;ls=m+1;}
            else if (a[m]>x){ld=m-1;}
            else if (a[m]<x){ls=m+1;}

        }
    return poz;
}
int bs1(int ls, int ld, int x)
{
    int m,poz;
    while (ls<=ld)
    {
        m=(ls+ld)/2;
        if (a[m]<=x){poz=m; ls=m+1;}
        else if (a[m]>x){ld=m-1;}
    }
    return poz;

}
int bs2(int ls, int ld, int x)
{
    int m,poz;
    poz=-1;
    while (ls<=ld)
        {
            m=(ls+ld)/2;
            if (a[m]>=x){poz=m; ld=m-1;}
            else if (a[m]<x){ls=m+1;}
        }
        return poz;
}


int main()
{
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>a[i];
    }
    f>>m;
    for (i=1;i<=m;i++)
    {
        f>>y>>x;
        if (y==0){q<<bs0(1,n,x)<<'\n';}
        else if (y==1){q<<bs1(1,n,x)<<'\n';}
        else if (y==2){q<<bs2(1,n,x)<<'\n';}
    }
    f.close();
    q.close();


}