#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int V[100001], N;

int cb0(int st, int dr, int x){
    int m;
    while(st <= dr){
        m = (st + dr) / 2;
        if( V[m] <= x ){
            st = m + 1;
        }
        else{
            dr = m - 1;
        }
    }
    m--;
    if(V[m] == x)
        return m;
    else
        return -1;
}

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

int cb2(int st, int dr, int x){
    int m;
    while(st <= dr){
        m = (st + dr) / 2;
        if( V[m] < x ){
            st = m + 1;
        }
        else{
            dr = m - 1;
        }
    }
    if( V[m] < x )
        m++;
    return m;
}

int main()
{
    int i, m, v, x;
    f >> N;
    for(i = 1; i <= N; i++)
        f >> V[i];
    f >> m;
    for(i = 1; i<=m; i++){
        f >> v;
        switch(v){
        case 0:
            f >> x;
            g << cb0(1,N,x) << '\n';
            break;
        case 1:
            f >> x;
            g << cb1(1,N,x) << '\n';
            break;
        case 2:
            f >> x;
            g << cb2(1,N,x) << '\n';
            break;
        }
    }
    return 0;
}