#include <fstream>

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

int caut0(int st, int dr, int y)
{
    int med;

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

int caut2(int st, int dr, int y)
{
    int med;
    while(st<=dr)
    {
        med=(st+dr)/2;
        if (a[med]<y) st=med+1;
        else  dr=med-1;
    }
    med=(st+dr)/2;
    if (a[med]<y) return med+1;
    return med;
}
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;
        else if (x==1) g << caut1(1, m, y) << endl;
            else g << caut2(1, m, y) << endl;

    }
    return 0;
}