#include<fstream>
#include<iostream>
#define maxn 100005

using namespace std;

int m, n;
int a[maxn];

int bs0(int x) {
    int m, pos = -1;
    int p = 1, u = n;
    while (p <= u) {
        m = (p+u)/2;
        if (x < a[m]) 
            u = m-1;  
        else {
            p = m+1;
            if (a[m] == x)
                pos = m;  
        }
    }     
    return pos;
}

int bs1(int x) {
    int m, p = 1, u = n;
    int pos = 0;
    while (p <= u) {
        m = (p+u)/2;
        if (x < a[m]) {
            u = m-1;
        }
        else {
            p = m+1;
            pos = m;    
        }    
    }
    return pos;
}

int bs2(int x) {
    int m, p = 1, u = n;
    int pos = n+1;
    while (p <= u) {
        m = (p+u)/2;
        if (x <= a[m]) {
            u = m-1;
            pos = m;    
        }    
        else {
            p = m+1;    
        }
    }
    return pos;
}
    

int main() {
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");   
    
    f >> n;
    int i, j, t, x;
    for (i = 1; i <= n; i++) 
        f >> a[i];
        
    f >> m;
    for (j = 1; j <= m; j++) {
        f >> t >> x;
        if (t == 0)
            g << bs0(x) << '\n';
        else 
            if (t == 1)
                g << bs1(x) << '\n';
            else
                g << bs2(x) << '\n';    
    }
    return 0;
}