import java.io.*;
import java.util.*;

public class Main {

	static class Task {

		class Pereche {
			int comanda;
			int numar;

			public Pereche(int a1, int a2) {
				comanda = a1;
				numar = a2;

			}
		}

		int n, m;
		ArrayList<Integer> numbers = new ArrayList<>();
		ArrayList<Pereche> comenzi = new ArrayList<>();

		public void read() {
			MyScanner sc = new MyScanner();
			n = sc.nextInt();

			for (int i = 0; i < n; i++) {
				numbers.add(sc.nextInt());
			}
			m = sc.nextInt();
			for (int i = 0; i < m; i++) {
				comenzi.add(new Pereche(sc.nextInt(), sc.nextInt()));
			}

		}
		private void writeOutput(ArrayList<Integer> result) {
			try {
				PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("cautbin.out")));
				for (int nr  : result) {
					pw.printf("%d\n",nr);
				}
				pw.close();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		
		public int cautare(int comanda, int numar) {
			
			int top = n-1,low = 0;
			int poz = -2;
			int mid;
			switch (comanda) {
			case 0:
				
				while(top-low > 0) {
					mid = low + (top - low)/2;
					
					if(numbers.get(mid) == numar) {
						poz = mid;
						low = mid+1;
						continue;
					}
					if(numbers.get(mid) > numar) {
						top = mid-1;
						continue;
					}
					if(numbers.get(mid) < numar) {
						low = mid+1;
						continue;
					}
				}
				return poz;
				
			case 1:
				
				while(top-low >= 0) {
					mid = low + (top - low)/2;
					if(numbers.get(mid) == numar) {
						
						poz = mid;
						low = mid+1;
						continue;
					}
					if(numbers.get(mid) > numar) {
						top = mid-1;
						
						continue;
					}
					if(numbers.get(mid) < numar) {
						
						if(poz <= mid) {
							poz = mid;
						}
						low = mid +1;
						continue;
					}
					
				}
				return poz;
			case 2:
				poz = 2000000;
				while(top-low >= 0) {
					mid = low + (top - low)/2;
					if(numbers.get(mid) == numar) {
						
						poz = mid;
						top = mid-1;
						continue;
					}
					if(numbers.get(mid) > numar) {
						top = mid-1;
						if(poz >=  mid) {
							poz = mid;
						}
						continue;
					}
					if(numbers.get(mid) < numar) {
						
						
					
						low = mid +1;
						continue;
					}
					
				}
				return poz;
			default:
				break;
			}
			return -2;
		}

		public void solve() {
			read();
			ArrayList<Integer> res = new ArrayList<>();
			for(Pereche p : comenzi) {
				res.add(cautare(p.comanda,p.numar)+1);
			}
			writeOutput(res);
		}

		
	}
	public static void main(String[] args) {

		new Task().solve();
	}
}


class MyScanner {
	BufferedReader br;
	StringTokenizer st;

	public MyScanner() {
		try {
			br = new BufferedReader(new InputStreamReader(new FileInputStream("cautbin.in")));
		} catch (FileNotFoundException e) {
			// TODO: handle exception
		}

	}

	String next() {
		while (st == null || !st.hasMoreElements()) {
			try {
				st = new StringTokenizer(br.readLine());
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
		return st.nextToken();
	}

	int nextInt() {
		return Integer.parseInt(next());
	}

	long nextLong() {
		return Long.parseLong(next());
	}

	double nextDouble() {
		return Double.parseDouble(next());
	}

	String nextLine() {
		String str = "";
		try {
			str = br.readLine();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return str;
	}
}