#include <iostream>
#include <stdio.h>
using namespace std;
int n,m,arr[100000 + 100];
void binarySearch0(int nr){
	int l = 0,r = n - 1;
	bool ok = false;
	while(l <= r){
		int m = l + ((r - l) >> 1);
			if(arr[m] <= nr){
				l = m + 1;
			}
			if(arr[m] > nr){
				r = m - 1;
			}
			if(arr[m] == nr && ((m + 1 < n && arr[m + 1] > arr[m]) || m == n - 1)){
				printf("%d\n",m + 1);
				ok = true;
				break;
			}
	}
	if(ok == false)
		printf("-1\n");

}
void binarySearch2(int nr){
	int l = 0,r = n - 1;
	bool ok = false;
	while(l <= r){
		int m = l + ((r - l) >> 1);
		if((m - 1 >= 0 && arr[m] == nr && arr[m - 1] == arr[m]) || arr[m] > nr){
			r = m - 1;
		}
		if(arr[m] < nr){
			l = m + 1;
		}
		if(arr[m] >= nr && ((m - 1 >= 0 && arr[m - 1] < arr[m] && arr[m - 1] < nr) || m == 0)){
			printf("%d\n",m + 1);
			ok = true;
			break;
		}

	}
	if(ok == false)
		printf("-1\n");

}
void binarySearch1(int nr){
	int l = 0,r = n - 1;
	bool ok = false;
	while(l <= r){
		int m = l + ((r - l) >> 1);
		if((m + 1 <= n && arr[m] == nr && arr[m + 1] == arr[m]) || arr[m] < nr){
			l = m + 1;
		}
		if(arr[m] > nr){
			r = m - 1;
		}
		if(arr[m] <= nr && ((m + 1 < n && arr[m] < arr[m + 1] && arr[m + 1] > nr) || m == n - 1)){
			printf("%d\n",m + 1);
			ok = true;
			break;
		}

	}
	if(ok == false)
		printf("-1\n");

}

int main(){
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%d",&n);
	for(int i = 0; i < n; i++){
		scanf("%d",&arr[i]);
	}
	scanf("%d",&m);
	for(int i = 0; i < m; i++){
		int q,x;
		scanf("%d%d",&q,&x);
		if(q == 0)
			binarySearch0(x);
		if(q == 1)
			binarySearch1(x);
		if(q == 2)
			binarySearch2(x);
	}
	return 0;
}