import java.io.*;


public class CautareBinara {
	static int arrDim;
	static int[] arr = new int[100000];
	static int questionsDim;
	static int [][] questions = new int[100000][2];
	public static void readData(String fileName){
		try{
			BufferedReader br = new BufferedReader(new FileReader(fileName));
			/*read dimension of array*/
			String currentLine = br.readLine();
			arrDim = Integer.parseInt(currentLine);
			
			//System.out.println(arrDim);
			/*read the array*/
			currentLine = br.readLine();
			String[] strings = currentLine.split(" ");
			
			for(int i = 0; i < arrDim; i++){
				arr[i] = Integer.parseInt(strings[i]);
				//System.out.print(arr[i] + " ");
			}
			/*read the number of questions*/
			currentLine = br.readLine();
			questionsDim = Integer.parseInt(currentLine);
			/*read questions*/
			for(int i = 0; i < questionsDim; i++){
				//System.out.println();
				currentLine = br.readLine();
				strings = currentLine.split(" ");
				for(int j = 0; j < 2; j++){
					questions[i][j] = Integer.parseInt(strings[j]);	
					//System.out.print(questions[i][j] + " ");
				}
				
			}
		}
		catch (Exception e){
			e.printStackTrace();
		}
		
	}
	
	public static int bs0(int x, int p, int u){
		int m;
		while(p <= u){
			m = (p + u)/2;
			if(arr[m] <= x )
				p = m + 1;
			else
				u = m - 1;			
		}
		m = (p + u)/2;
		if(arr[m] > x)
			m--;
		if(arr[m] == x)
			return m + 1;
		
		return -1;			
	}
	
	public static int bs1(int x, int p, int u){
		int m;
		while(p < u){
			m = (p + u)/2;
			if(arr[m] <= x)
				p = m + 1;
			else
				u = m;
		}
		m = (p + u)/2;
		if(arr[m] > x)
			--m;
		return m + 1;		
	}
	
	public static int bs2(int x, int p, int u){
		int m;
		while(p < u){
			m = (p + u)/2;
			if(arr[m] < x)
				p = m + 1;
			else
				u = m;
		}
		m = (p + u) / 2;
		if(arr[m] < x)
			m++;
		return m + 1;
	}
	
	
	public static void main(String[] argv) throws Exception{
		
		File statText = new File("cautbin.out");
		FileOutputStream is = new FileOutputStream(statText);
		OutputStreamWriter osw = new OutputStreamWriter(is);    
		Writer w = new BufferedWriter(osw);
		
		readData("cautbin.in");
				
		for(int i = 0; i < questionsDim; i++){
			if(questions[i][0] == 0)
				w.write("" + bs0(questions[i][1], 0, arrDim) + "\n");
			if(questions[i][0] == 1)
				w.write("" + bs1(questions[i][1], 0, arrDim) + "\n");
			if(questions[i][0] == 2)
				w.write("" + bs2(questions[i][1], 0, arrDim) + "\n");
		}
		w.close();
	}
}