#include <algorithm>
#include <cstdio>
using namespace std;
int a[100100];
int main () {
    int n,m,x,y,i,t;
    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,&y);
        if (t == 0) {
            x = upper_bound(a+1,a+n+1, y)-a-1;
            if (x <= n&&x>=1&&a[x]==y)
                printf("%d\n", x);
            else
                printf("-1\n");
        } else if (t==1) {
            x=lower_bound(a+1,a+n+1,y+1)-a-1;
            printf("%d\n", x);
        } else {
            x = upper_bound(a+1,a+n+1,y-1)-a;
            printf("%d\n", x);
        }
    }
    return 0;
}