#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
const int nmax = 100005;
int a[nmax];
int n, q;

int main(){
    ios::sync_with_stdio(0);
    f.tie(0);
    f >> n;
    for(int i = 1; i <= n; i++){
        f >> a[i];
    }
    f >> q;
    while(q--){
        int t, x;
        f >> t >> x;
        if(t == 0){
            int p = upper_bound(a + 1, a + n + 1, x) - a;
            if(p - 1 > 0 && a[p - 1] == x){
                g << p - 1 << '\n';
            }
            else g << "-1\n";
        }
        else if(t == 1){
            int p = upper_bound(a + 1, a + n + 1, x) - a;
            if(p - 1 > 0){
                g << p - 1 << '\n';
            }
            else g << "-1\n";
        }
        else if(t == 2){
            int p = lower_bound(a + 1, a + n + 1, x) - a;
            if(p <= n){
                g << p << '\n';
            }
            else g << "-1\n";
        }
    }
}