//package pregTest;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Scanner;

class Intrebare{
	private int comanda;
	private int conditie;
	public int getComanda() {
		return comanda;
	}
	public void setComanda(int comanda) {
		this.comanda = comanda;
	}
	public int getConditie() {
		return conditie;
	}
	public void setConditie(int conditie) {
		this.conditie = conditie;
	}
	public Intrebare(int comanda, int conditie) {
		super();
		this.comanda = comanda;
		this.conditie = conditie;
	}
	
}

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n = 0 ;
		int sir[] = null ;
		int m = 0 ;
		ArrayList<Intrebare> q = null ;
		try {
			Scanner fileScanner = new Scanner(new FileInputStream("cautbin.in"));
			n = fileScanner.nextInt();
			sir = new int[n];
			for ( int i = 0; i < n ;i++){
				sir[i] = fileScanner.nextInt();
			}
			m = fileScanner.nextInt();
			q= new ArrayList<Intrebare>(m);
			for (int i = 0 ; i<m ; i++){
				int prim = fileScanner.nextInt();
				int sec= fileScanner.nextInt();
				Intrebare q1 = new Intrebare(prim,sec);
				q.add(i, q1);
			}
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		int r[] = new int[m];
		for(int i = 0 ; i<m ; i++){
			if(q.get(i).getComanda() == 0){
				 r[i] = cautaBinar0(sir,0,n,q.get(i).getConditie());
				//System.out.println(r[i]);
			}
			if(q.get(i).getComanda() == 1){
				 r[i] = cautaBinar1(sir,0,n,q.get(i).getConditie());
				//System.out.println(r[i]);
			}
			if(q.get(i).getComanda() == 2){
				 r[i] = cautaBinar2(sir,0,n,q.get(i).getConditie());
				//System.out.println(r[i]);
			}
		try {
			PrintWriter writer = new PrintWriter("cautbin.out");
			for(int j = 0 ;j<m ; j++){
				writer.write(String.valueOf(r[j])+"\n");
			}
			writer.close();
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
			
		}
		
		
	}

	private static int cautaBinar2(int[] sir, int low, int upper, int conditie) {
		// TODO Auto-generated method stub
		int mid = low+(upper-low)/2;
		if(low == upper) return mid;
			
		if(sir[mid] <conditie) return cautaBinar1(sir,mid+1,upper,conditie);
		else return cautaBinar1(sir,low,mid-1,conditie);
		
	}

	private static int cautaBinar1(int[] sir, int low, int upper, int conditie) {
		// TODO Auto-generated method stub
		int mid = low+(upper-low)/2;
		if(low == upper) return mid+1;
			
		if(sir[mid] <= conditie) return cautaBinar1(sir,mid+1,upper,conditie);
		else return cautaBinar1(sir,low,mid-1,conditie);
		
		
	}

	private static int cautaBinar0(int[] sir, int low, int upper,int conditie) {
		if(low > upper) return -1;
		int mid = low+(upper-low)/2;
		if(sir[mid] == conditie) {
				if(mid < cautaBinar0(sir,mid+1,upper,conditie))
					return cautaBinar0(sir,mid+1,upper,conditie);
				else return mid+1;
		}
		else if(sir[mid] < conditie) return cautaBinar0(sir,mid+1,upper,conditie);
		else return cautaBinar0(sir,low,mid-1,conditie);
		
		// TODO Auto-generated method stub
	}
		
	}