#include <fstream>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int binary1(int n, int value, int v[])
{
    int li=1, lf=n, poz=0;

    while(li<=lf)
    {
        int mid=(li+lf)/2;

        if(v[mid]==value)
            poz=mid, li=mid+1;
        else if(v[mid]<value)
            li=mid+1;
        else
            lf=mid-1;
    }

    if(v[poz]==value)
        return poz;

    return -1;
}

int binary2(int n, int value, int v[])
{
    int li=1, lf=n, poz=0;

    while(li<=lf)
    {
        int mid=(li+lf)/2;

        if(v[mid]<=value)
            poz=mid, li=mid+1;
        else
            lf=mid-1;
    }

    return poz;
}

int binary3(int n, int value, int v[])
{
    int li=1, lf=n, poz=0;

    while(li<=lf)
    {
        int mid=(li+lf)/2;

        if(v[mid]>=value)
            poz=mid, lf=mid-1;
        else
            li=mid+1;
    }

    return poz;
}

int main()
{
    int n, m, v[100010];
    fin >> n;

    for(int i=1; i<=n; i++)
        fin >> v[i];

    fin >> m;

    for(int j=1;j<=m;j++)
    {
        int cerinta, val;
        fin >> cerinta >> val;

        if(cerinta==0)
            fout << binary1(n,val,v) << "\n";

        else if(cerinta==1)
            fout << binary2(n,val,v) << "\n";

        else if(cerinta==2)
            fout << binary3(n,val,v) << "\n";
    }

    return 0;
}