#include <iostream>
#include <fstream>
#define N 100010
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int v[N];
int cb(int ls, int ld, int x)
{
    int m;
    while (ls <= ld) {
        m = (ls + ld) / 2;
        if (v[m] <= x)
            ls = m + 1;
        else
            ld = m - 1;
    }
    m = (ls + ld) / 2;

    if (v[m] > x) m --;
    if (v[m] == x)
        return m;
    return -1;
}
int cb1(int ls, int ld, int x)
{
    int m;
    while (ls < ld) {
        m = (ls + ld) / 2;
        if (v[m] <= x)
            ls = m + 1;
        else
            ld = m;
    }
    m = (ls + ld) / 2;
    if (v[m] > x) --m;
        return m;
}
int cb2(int ls, int ld, int x)
{
    int m;
    while (ls < ld) {
        m = (ls + ld) / 2;
        if (v[m] < x)
            ls = m + 1;
        else
            ld = m;
    }
    m = (ls + ld) / 2;
    if (v[m] < x) ++m;
        return m;
}
int main()
{
    int n,i,j,a,b,m;
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
    f>>m;
    for(j=1;j<=m;j++)
    {
        f>>a;
        f>>b;
        if(a==0){ g<<cb(1,n,b); g<<'\n'; }
        if(a==1){ g<<cb1(1,n,b); g<<'\n'; }
        if(a==2) { g<<cb2(1,n,b); g<<'\n'; }
    }
    f.close();
    g.close();
}