package problema1;

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

class DifferentBinarySearches {
	// cea mai mare pozitie a numarului cautat sau -1
	public static int firstOne (int[] v, int number) {
		int low = 0;
		int high = v.length - 1;
		int mid = -1;
		
		while (low <= high) {
			mid = low + (high - low) / 2;
			if (number >= v[mid]) {
				low = mid + 1;
			} else {
				high = mid - 1;
			}
		}
		
		if (v[mid] > number) {
			mid--;
		}
		
		if (number == v[mid]) {
			return mid;
		}
		
		return -1;
	}
	
	// cea mai mare pozitie a unui numar mai mic sau egal cu number
	public static int secondOne (int[] v, int number) {
		int low = 0;
		int high = v.length - 1;
		int mid = -1;
		
		while (low <= high) {
			mid = low + (high - low) / 2;
			if (number >= v[mid]) {
				low = mid + 1;
			} else {
				high = mid - 1;
			}
		}
		
		if (mid > 0 && v[mid] > number) {
			mid--;
		}
		
		return mid;
	}
	
	// cea mai mica pozitie a unui numar mai mare sau egal cu number
	public static int thirdOne (int[] v, int number) {
		int low = 0;
		int high = v.length - 1;
		int mid = -1;
		
		while (low <= high) {
			mid = low + (high - low) / 2;
			if (number > v[mid]) {
				low = mid + 1;
			} else {
				high = mid - 1;
			}
		}
		
		if (mid < v.length - 1 && v[mid] < number) {
			mid++;
		}
		
		return mid;
	}
}

class TestClass {
	public static void main(String[] args) throws IOException {
		Scanner input = new Scanner(new File("cautbin.in"));
		BufferedWriter output = new BufferedWriter(new FileWriter("cautbin.out"));

		// read the size of the array
		int n = input.nextInt();
		int[] v = new int[n];

		// read the elements of the array
		for (int i = 0; i < n; i++) {
			v[i] = input.nextInt();
		}

		// read the number of querries
		int m = input.nextInt();
		for (int i = 0; i < m; i++) {
			int command = input.nextInt();
			int number = input.nextInt();

			switch(command) {
				case 0 :
					int rez = DifferentBinarySearches.firstOne(v, number);
					output.write((rez + 1) + "\n");
					break;
				case 1 :
					rez = DifferentBinarySearches.secondOne(v, number);
					output.write((rez + 1) + "\n");
					break;
				case 2 :
					rez = DifferentBinarySearches.thirdOne(v, number);
					output.write((rez + 1) + "\n");
					break;
			}
		}
		
		output.close();
		input.close();
	}

}