package org.example.pregatire.DivideEtImpera;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;


        int n = Integer.parseInt(br.readLine()); // читаем n
        st = new StringTokenizer(br.readLine()); // читаем строку с массивом
        int[] numbers = new int[n];
        for (int i = 0; i < n; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }

        int m = Integer.parseInt(br.readLine()); // читаем m
        List<int[]> questions = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            questions.add(new int[] {a, b});
        }

        br.close();

        // ==========================================================================================

        StringBuilder sb = new StringBuilder();

        for (int[] question : questions) {
            int t = question[0];
            int x = question[1];

            if (t == 0) sb.append(binarySearch0(numbers, x));
            else if (t == 1) sb.append(binarySearch1(numbers, x));
            else if (t == 2) sb.append(binarySearch2(numbers, x));

            sb.append('\n');
        }

        System.out.println(sb);
    }

    private static int binarySearch0(int[] nums, int x) {
        int pos = -1;
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (x < nums[mid]) {
                right = mid - 1;
            } else if (x > nums[mid]) {
                left = mid + 1;
            } else {
                pos = mid;
                left = mid + 1;
            }
        }

        return pos + 1;
    }

    private static int binarySearch1(int[] nums, int x) {
        int pos = -1;
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (x < nums[mid]) {
                right = mid - 1;
            } else if (x > nums[mid]) {
                pos = mid;
                left = mid + 1;
            } else {
                pos = mid;
                left = mid + 1;
            }
        }

        return pos + 1;
    }

    private static int binarySearch2(int[] nums, int x) {
        int pos = -1;
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (x < nums[mid]) {
                right = mid - 1;
                pos = mid;
            } else if (x > nums[mid]) {
                left = mid + 1;
            } else {
                pos = mid;
                right = mid - 1;
            }
        }

        return pos + 1;
    }
}