#include <stdio.h>
#define NMAX 100005

int A[NMAX];
int n;

int main()
{
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
    int i, val, nr, type, step, lg;
    scanf("%d", &n);
    for (i=1; i<=n; ++i)
        scanf("%d", &A[i]);
    scanf("%d", &nr);
    for (step=1; step<=n; step<<=1);
    while (nr--) {
        scanf("%d %d", &type, &val);
        if (type < 2) {
	for (lg=step, i=0; lg; lg>>=1)
	    if (i+lg<=n && A[i+lg]<=val)
	        i+=lg;
	if (!type && A[i] != val)
	    printf("-1\n");
	else 
	    printf("%d\n", i);
        }
        else {
	for (lg=step, i=n; lg; lg>>=1)
	    if (i-lg>0 && A[i-lg]>=val)
	        i-=lg;
	printf("%d\n", i);
        }

    }
    return 0;
}