#include <fstream>

using namespace std;
int a[100005];
int caut1(int st, int dr, int y)
{
    int med, afis;
    while(st<=dr)
    {
        med=(st+dr)/2;
        if (a[med]>y) dr=med-1;
        else {afis=med; st=med+1;}
    }
    return afis;
}

int caut0(int st, int dr, int y)
{
    int afis=-1, med;

    while(st<=dr)
    {   med=(st+dr)/2;
        if (a[med]>y) dr=med-1;
        else if (a[med]<y) st=med+1;
             else {afis=med; st=med+1;}
    }
    return afis;
}

int caut2(int st, int dr, int y)
{
    int med, afis;
    while(st<=dr)
    {
        med=(st+dr)/2;
        if (a[med]<y) st=med+1;
        else {afis=med; dr=med-1;}
    }
    return afis;
}
int main()
{
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");

    int m, n, i, x, y;
    f >> m;
    for(i=1; i<=m; i++)
    f >> a[i];
    f >> n;
    for (i=1; i<=n; i++)
    {
        f >> x >> y;
        if (x==0) g << caut0(1, m, y) << endl;
        if (x==1) g << caut1(1, m, y) << endl;
        if (x==2) g << caut2(1, m, y) << endl;

    }
    return 0;
}