#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;
        else st=med;
    }
    if(a[dr]<=x) return dr;
        else return st;
}

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

    while(st<=dr)
    {   med=(st+dr)/2;
        if (a[med]>y) dr=med;
        else st=med;
    }
    if(a[dr]==x) return dr;
        else if(a[st]==x) return st;
            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;
        else  dr=med;
    }
    if(a[dr]<=x) return dr;
        else return st;
}
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;
}