#include<iostream>
#include<fstream>

using namespace std;

int a[100010];

int bsearch0(int p, int u, int x){
    int m, sol = 0;
    
    while (p <= u){
        m = (p+u)/2;
        if (a[m] <= x){
            sol = m;
            p = m+1;
        }
        else 
            u = m-1;
    }
    
    if (sol == 0 || a[m] != x)
        return -1;
    return sol;   
}

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

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


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