// proj2.cpp : Defines the entry point for the console application.
//

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

typedef struct {
	long pos;
	long lpos;
} globals;
globals gl = { 0 };

long FindNumber0(long*vector, long vsize, long target)
{
	
	while (true) {
		if (vector[gl.pos] < target) {
			gl.pos--;
		} else {
			if (vector[gl.pos] == target) {
				if (gl.lpos < gl.pos) {
					gl.lpos = gl.pos;
					return gl.pos;
				}
			}
			gl.pos++;
		}
		if (vsize - 1 == gl.pos) {
			break;
		}
	}
	return -2;
}

long FindNumber1(long*vector, long vsize, long target)
{

	while (true) {
		if (vector[gl.pos] < target) {
			gl.pos--;
		} else {
			if (vector[gl.pos] <= target) {
				if (gl.lpos < gl.pos) {
					gl.lpos = gl.pos;
					return gl.pos;
				}
			}
			gl.pos++;
		}
		if (vsize - 1 == gl.pos) {
			break;
		}
	}
	return -2;
}

long FindNumber2(long*vector, long vsize, long target)
{
	for (long i = 0; i < vsize; i++) {
		if (vector[i] <= target) {
			return i;
		}
	}
	return -2;
}

long main()
{
	FILE *file = fopen("cautbin.in", "rt");
	FILE *out = fopen("cautbin.out", "wt");
	long *vector = NULL;
	long lng = 0;
	long questions = 0;
	long answer = 0, response = 0;
	long target = 0;
	long ID = 0;
	bool found = 0;
	fscanf(file, "%ld ", &lng);
	vector = (long *)malloc(lng * sizeof(long));
	for (long i = 0; i < lng; i++) {
		fscanf(file, "%ld ", &vector[i]);
	}
	fscanf(file, "%ld ", &questions);
	for (long i = 0; i < questions; i++) {
		fscanf(file, "%ld ", &ID);
		answer = 0;
		response = 0;
		gl.lpos = 0;
		if (ID == 0) {
			fscanf(file, "%ld ", &target);
			gl.pos = lng / 2;
			while (answer != -2) {
				response = answer;
				answer = FindNumber0(vector, lng, target); 
			}
			fprintf(out, "%ld\r\n", response + 1);
		}
		if (ID == 1) {
			fscanf(file, "%ld ", &target);
			gl.pos = lng / 2;
			while (answer != -2) {
				response = answer;
				answer = FindNumber1(vector, lng, target);
			}
			fprintf(out, "%ld\r\n", response + 1);
		}
		if (ID == 2) {
			response = FindNumber2(vector, lng, target);
			fprintf(out, "%ld\r\n", response + 1);
		}
	}
	return 0;
}