#include <stdio.h>
#include <stdlib.h>

void readArray(FILE *in, int *v, int N);
void printArray(int *v, int N);
void readOperation(FILE *in, FILE *out, int *v, int N);
void swap(int *a, int *b);
int operation0(int *v, int lower, int upper, int key);
int operation1(int *v, int lower, int upper, int key);
int operation2(int *v, int lower, int upper, int key);


void swap(int *a, int *b){
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
}

int operation0(int *v, int lower, int upper, int key){
	// rightMost
	int pos;
	if(lower <= upper){
		pos = lower + (upper - lower) / 2;

		if(v[pos] == key){
			if(pos + 1 <= upper && v[pos + 1] == key){
				return operation0(v, pos + 1, upper, key);
			}
			return pos;
		} 
		if(v[pos] > key){
			return operation0(v, lower, pos - 1, key);
		}
		else{
			return operation0(v, pos + 1, upper, key);
		}
	}
	return -1;
}


int operation1(int *v, int lower, int upper, int key){
	// rightMost
	int pos;
	if(lower <= upper){
		pos = lower + (upper - lower) / 2;

		if(v[pos] <= key){
			if(pos + 1 <= upper && v[pos + 1] <= key){
				return operation1(v, pos + 1, upper, key);
			}
			return pos;
		} 
		else{
			return operation1(v, lower, pos - 1, key);
		}
		//else{
		//	return operation1(v, pos + 1, upper, key);
		//}
	}
	return -1;
}

int operation2(int *v, int lower, int upper, int key){
	// 2 x - cea mai mica pozitie pe care se afla un element cu valoarea mai mare sau egala 
	//cu x in sir. Se garanteaza ca cel mai mare numar din sir este mai mare sau egal decat x
	printf("I am here\n");

	int pos;
	if(lower <= upper){
		pos = lower + (upper - lower) / 2;

		if(v[pos] >= key){
			if(pos - 1 >= lower && v[pos - 1] >= key){
				return operation2(v, lower, pos - 1, key);
			}
			return pos;
		} 
		// if(v[pos] > key){
		// 	return operation1(v, lower, pos - 1, key);
		// }
		else{
			return operation2(v, pos + 1, upper, key);
		}
	}
	return -1;
}

void readArray(FILE *in, int *v, int N){
	for(int i = 0; i < N; i++){
		fscanf(in, "%d", v + i);
	}
}

void printArray(int *v, int N){
	for(int i = 0; i < N; i++){
		printf("%d ", v[i]);
	}
	printf("\n");
}

void readOperation(FILE *in, FILE *out, int *v, int N){
	int M, type, value;
	fscanf(in, "%d", &M);
	for(int i = 0; i < M; i++){
		fscanf(in, "%d", &type);
		fscanf(in, "%d", &value);
		switch(type){
			case 0:{
				int op = operation0(v, 0, N-1, value);
				if( op == -1){
					fprintf(out, "%d\n", -1);
				}
				else{
					fprintf(out, "%d\n", op + 1);
				}
				break;
			}
			case 1:{
				fprintf(out, "%d\n", operation1(v, 0, N-1, value) + 1);
				break;
			}
			case 2:{
				fprintf(out, "%d\n", operation2(v, 0, N-1, value) + 1);
				break;
			}
		}
	}
}

int main(){
	FILE *in, *out;
	int N, *v;
	in = fopen("cautbin.in", "r");
	out = fopen("cautbin.out", "w");

	fscanf(in, "%d", &N);

	v = malloc(N * sizeof(int));

	readArray(in, v, N);
	readOperation(in, out, v, N);

	free(v);
	fclose(in);
	fclose(out);
	return 0;
}