#include <cstdio>
#include <algorithm>
using namespace std;

int n, i, m, a[100010], x, poz, t;
int main ()
{
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);

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