#include <cstdio>
#include <algorithm>


using namespace std;

int n;
int a[100010];

void citire(){
    scanf ("%d", &n);
    for (int i = 0; i < n; ++ i){
        scanf ("%d", &a[i]);
    }
    int m;
    for (scanf ("%d", &m); m --;){
        int caz;
        int x;
        scanf ("%d %d", &caz, &x);
        if (caz == 0){
            int poz = upper_bound(a, a + n, x) - a;
            if (!(poz >= 0 && a[poz - 1] == x)){
                poz = -1;
            }
            printf ("%d\n", poz);
        }else if (caz == 1){
            printf ("%d\n", upper_bound (a, a + n, x) - a);
        }else{
            printf ("%d\n", lower_bound (a, a + n, x) - a + 1);
        }
    }
}

int main()
{
    freopen ("cautbin.in", "r", stdin);
    freopen ("cautbin.out", "w", stdout);

    citire();

    return 0;
}