#include <iostream>
#include <cstdio>

using namespace std;

int a[100005], n, m, p;

int putere(int p){
    if(p >= n)
        return p;
    return putere(p*2);
}

void citire(){
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    cin >> m;
}

int caut_0_1(int x){
    int i, l;
    for(i = 0, l = p; l > 0; l >>= 1)
        if(i + l <= n && a[i+l] <= x)
            i += l;
    if(a[i] <= x)
        return i + 1;
    return -1;
}

int caut_2(int x){
    int i, l;
    for(i = 0, l = 1; l <= p; l <<= 1){
        if(i + l <= n && a[i+l] >= x)
            i += l;
        if(a[i] >= x)
            return i + 1;
    }
    return -1;
}

int main()
{
    freopen("cautbin.in", "r", stdin);
    citire();
    p = putere(1);
    for(int i = 0; i < m; i++){
        int v, x;
        cin >> v >> x;
        if(v == 0 || v == 1){
            cout << caut_0_1(x) << '\n';
            continue;
        }
        if(v == 2){
            cout << caut_2(x) << '\n';
            continue;
        }
    }
    return 0;
}