#include <stdio.h>

int a[100001];
int n, m;
int i, j, k;
int Cbin0(int st, int dr);
int Cbin1(int st, int dr);
int Cbin2(int st, int dr);

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 ( k = 1; k <= m; k++ )
	{
		scanf ("%d %d", &i, &j);
		if ( i == 0 ) printf("%d\n", Cbin0(1, n));
		if ( i == 1 ) printf("%d\n", Cbin1(1, n));
		if ( i == 2 ) printf("%d\n", Cbin2(1, n));
	}
	return 0;
}

int Cbin0(int st, int dr)
{
	if (st == dr) 
	{
		if ( a[st] == j ) return st;
		return -1;
	}
	int mid = st + (dr-st)/2;
	if ( a[mid+1] <= j ) return Cbin0(mid+1, dr);
	return Cbin0(st, mid);
}

int Cbin1(int st, int dr)
{
	if (st == dr) return st;

	int mid = st + (dr-st)/2;
	if ( a[mid+1] <= j ) return Cbin1(mid+1, dr);
	return Cbin1(st, mid);
}

int Cbin2(int st, int dr)
{
	if (st == dr) return st;
	int mid = st + (dr-st)/2;
	if ( a[mid] >= j ) return Cbin2(st, mid);
	return Cbin2(mid+1, dr);
}