#include <fstream>
#define n_max 100002

using namespace std;

ifstream r("cautbin.in");
ofstream w("cautbin.out");

long v[n_max];
long n,m,task,x;

long cbin0(long st, long dr, long x) {
    long m;
    while (st<=dr) {
        m=(st+dr)/2;
        if (v[m]<=x)
            st=m+1;
        else
            dr=m-1;
    }
    m=(st+dr)/2;
    if (v[m]>x)
        m=m-1;
    if (v[m]==x)
        return m;
    else
        return -1;
}

long cbin1(long st, long dr, long x) {
    long m;
    while (st<=dr) {
        m=(st+dr)/2;
        if (v[m]<=x)
            st=m+1;
        else
            dr=m-1;
    }
    if (v[m]>x)
        m=m-1;
    return m;
}

long cbin2(long st, long dr, long x) {
    long m;
    while (st<=dr) {
        m=(st+dr)/2;
        if (v[m]<x)
            st=m+1;
        else
            dr=m-1;
    }
    m=(st+dr)/2;
    if (v[m]<x)
        m=m+1;
    return m;
}

int main() {
    long i;
    r>>n;
    for (i=1; i<=n; i++)
        r>>v[i];
    r>>m;
    for (i=1; i<=m; i++) {
        r>>task>>x;
        if (task==0)
            w<<cbin0(1,n,x) <<"\n";
        else
        if (task==1)
            w<<cbin1(1,n,x) <<"\n";
        else
            w<<cbin2(1,n,x) <<"\n";
    }
    r.close();
    w.close();
    return 0;
}