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

public class Main {

    public static void main(String[] args) throws IOException {
        InputStream inputStream = new FileInputStream("cautbin.in");
        OutputStream outputStream = new FileOutputStream("cautbin.out");

        try (InputReader inputReader = new InputReader(inputStream);
            PrintWriter printWriter = new PrintWriter(outputStream)) {
            int N = inputReader.nextInt();
            int[] sortedArray = new int[N];
            for (int i = 0; i < N; i++) {
                sortedArray[i] = inputReader.nextInt();
            }

            int queries = inputReader.nextInt();
            for (int queryNo = 0; queryNo < queries; queryNo++) {
                int type = inputReader.nextInt();
                int value = inputReader.nextInt();

                int result;
                switch (type) {
                    case 0:
                        result = BinarySearchUtils.largestPosForElem(sortedArray, value);
                        break;
                    case 1:
                        result = BinarySearchUtils.largestPosSmallerThanOrEqual(sortedArray, value);
                        break;
                    case 2:
                        result = BinarySearchUtils.smallestPosLargerThanOrEqual(sortedArray, value);
                        break;
                    default:
                        throw new RuntimeException("Found unexpected type: " + type);
                }

                if (result < 0) {
                    assert type == 0;
                    printWriter.println(result);
                } else {
                    printWriter.println(result + 1);
                }
            }
        }
    }

    static class BinarySearchUtils {

        public static int largestPosForElem(int[] sorted, int no) {
            if (no < sorted[0]) {
                return -1;
            }

            int candidatePos = largestPosSmallerThanOrEqual(sorted, no);
            return sorted[candidatePos] == no ? candidatePos : -1;
        }

        public static int largestPosSmallerThanOrEqual(int[] sorted, int no) {
            assert sorted[0] <= no;
            // INV: sorted[low] <= no < sorted[high]
            int low = 0, high = sorted.length;
            while (high - low > 1) {
                int mid = low + (high - low) / 2;
                if (sorted[mid] <= no) {
                    low = mid;
                } else {
                    high = mid;
                }
            }

            return low;
        }

        public static int smallestPosLargerThanOrEqual(int[] sorted, int no) {
            assert sorted[sorted.length - 1] >= no;

            // INV: sorted[low] < no <= sorted[high]
            int low = -1, high = sorted.length - 1;
            while (high - low > 1) {
                int mid = low + (high - low) / 2;
                if (sorted[mid] < no) {
                    low = mid;
                } else {
                    high = mid;
                }
            }

            return low + 1;
        }
    }

    static class InputReader implements AutoCloseable {

        private BufferedReader bufferedReader;

        private StringTokenizer stringTokenizer;

        public InputReader(InputStream inputStream) {
            this.bufferedReader = new BufferedReader(new InputStreamReader(inputStream));
            stringTokenizer = null;
        }

        private String nextToken() {
            if (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
                try {
                    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return stringTokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(nextToken());
        }

        @Override
        public void close() throws IOException {
            bufferedReader.close();
        }
    }
}