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) {
		if (l > r) {
			return -2;
		}
		int m = (l + r) / 2;
		if (sch == array[m]) {
			if (m < array.length - 1 && array[m + 1] == sch) {
				return binSch0(m + 1, r);
			}
			return m;
		}
		if (sch < array[m]) {
			return binSch0(l, m - 1);
		}
		return binSch0(m + 1, r);
	}

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

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

	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();
			// System.out.println(val + " " + op);
			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();
	}

}