#include <stdio.h>

#define N 100000

long cautbin_0(long [], long, long, long);
long cautbin_1(long [], long, long, long);
long cautbin_2(long [], long, long, long);

int main(void) {

    long n, m, a[N], elem, i;
    short intrb;

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

    scanf("%ld", &n);

    for(i = 0; i < n; ++i)
        scanf("%ld", &a[i]);

    scanf("%ld", &m);

    for(i = 0; i < m; ++i) {

        scanf("%hd %ld", &intrb, &elem);

        switch(intrb) {

            case 0:
                printf("%ld\n", cautbin_0(a, elem, 0, n));
                break;
            case 1:
                printf("%ld\n", cautbin_1(a, elem, 0, n));
                break;
            case 2:
                printf("%ld\n", cautbin_2(a, elem, 0, n));
                break;
        }
    }

    return 0;
}

long cautbin_0(long a[], long elem, long lo, long hi) {

    long mid;
    
    while(lo <= hi) {

        mid = lo + (hi - lo) / 2;

        if(a[mid] <= elem)
            lo = mid + 1;
        else
            hi = mid - 1;
    }

    mid = lo + (hi - lo) / 2;

    if(a[mid] > elem)
        --mid;
    if(a[mid] == elem)
        return mid + 1;
    return -1;
}

long cautbin_1(long a[], long elem, long lo, long hi) {

    long mid;

    while(lo < hi) {

        mid = lo + (hi - lo) / 2;

        if(a[mid] <= elem)
            lo = mid + 1;
        else
            hi = mid;
    }

    mid = lo + (hi - lo) / 2;

    if(a[mid] > elem)
        --mid;
    return mid + 1;
}

long cautbin_2(long a[], long elem, long lo, long hi) {

    long mid;

    while(lo < hi) {

        mid = lo + (hi - lo) / 2;

        if(a[mid] < elem)
            lo = mid + 1;
        else
            hi = mid;
    }

    mid = lo + (hi - lo) / 2;

    if(a[mid] < elem)
        ++mid;
    return mid + 1;
}