#include <iostream>
#include <fstream>
#define N 100010
std::ifstream cin("cautbin.in");
std::ofstream cout("cautbin.out");
int v[N];
int bsearch0(int st, int dr, int key){
    int m;
    while(st <= dr){
        m = (st+dr)/2;
        if(v[m] <= key)
            st = m+1;           //clasica
        else dr = m-1;
    }
    m = (st+dr)/2;
    if(v[m] > key) m--;
    if(v[m] == key) return m;
    return -1;
}
int bsearch1(int st, int dr, int key){
    int m, n = st;
    while(st < dr){
        m = (st+dr)/2;
        if(v[m] <= key)
            st = st + 1;
        else dr = m;
    }
    m = (st+dr)/2;
    if(v[m] > key) --m;
    return m;
}
int bsearch2(int st, int dr, int key){
    int m;
    while(st < dr){
        m = (st+dr)/2;
        if(v[m] < key)
            st = m+1;
        else dr = m;
    }
    m = (st+dr)/2;
    if(v[m] < key) ++m;
    return m;
}
int main(){
    int i, n, m, tip, val;
    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> v[i];
    cin >> m;
    while(m--){
        cin >> tip >> val;
        if(tip == 0)
            cout << bsearch0(1,n,val) << '\n';
        if(tip == 1)
            cout << bsearch1(1,n,val) << '\n';
        if(tip == 2)
            cout << bsearch2(1,n,val) << '\n';
    }

}