import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Scanner;

public class Main {
	final String input;
	final String output;
	int n;
	int m;
	int op;
	int[] array;
	int sch;

	int binSch0(int l, int r) {
		while (true) {
			
			if (l > r) {
				return -2;
			}
			int m = (l + r) / 2;
			if (sch == array[m]) {
				if (m < array.length - 1 && array[m + 1] == sch) {
					l = m + 1;
					continue;
				}
				return m;
			}
			if (sch < array[m]) {
				r = m - 1;
				continue;
			}
			l = m + 1;
		}
	}

	int binSch1(int l, int r) {
		while (true) {
			int m = (l + r) / 2;
			if (array[m] <= sch) {
				if (m == array.length - 1 || array[m + 1] > sch) {
					return m;
				}
				l = m + 1;
				continue;
			}
			r = m - 1;
		}
	}

	int binSch2(int l, int r) {
		while (true) {
			int m = (l + r) / 2;
			if (array[m] >= sch) {
				if (m == 0 || array[m - 1] < sch) {
					return m;
				}
				r = m - 1;
				continue;
			}
			l = m + 1;
		}
	}

	Main(String input, String output) {
		this.input = input;
		this.output = output;
	}

	public void solve() throws IOException {
		Scanner scanner = new Scanner(new FileReader(input));
		BufferedWriter writer = new BufferedWriter(new FileWriter(output));
		n = scanner.nextInt();
		array = new int[n];
		for (int i = 0; i < n; i++) {
			array[i] = scanner.nextInt();
		}
		m = scanner.nextInt();
		for (int i = 0; i < m; i++) {
			int op = scanner.nextInt();
			sch = scanner.nextInt();
		
			switch (op) {
			case 0:
				writer.write(binSch0(0, array.length) + 1 + "\n");
				break;
			case 1:
				writer.write((binSch1(0, array.length) + 1) + "\n");
				break;
			case 2:
				writer.write(binSch2(0, array.length) + 1 + "\n");
				break;
			}
		}
		writer.flush();
	}

	public static void main(String[] args) throws IOException {
		Main main = new Main("cautbin.in", "cautbin.out");
		main.solve();
	}

}