#include <iostream>
#include <cstdio>

using namespace std;

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

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

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

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

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