#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-st+1)/ 2;//vrem ca mijlocul sa fie rotunjit in sus ca sa evitam posibilitatea buclei infinite
        if( V[m] == x ){
            st = m;
        }
        else if(V[m]<x){
            st = m + 1;
        }
        else
            dr = m - 1;
    }
    if( V[st] == x )
        return st;
    else
        return -1;
}

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

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

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;
}