给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。

第一行包含一个数n，表示序列长度。

第二行包含n个正整数，表示给定的序列。

第三个包含一个正整数m，表示询问个数。

接下来m行，每行三个数l,r,K，表示询问序列从左往右第l个数到第r个数中，从大往小第K大的数是哪个。序列元素从1开始标号。

对于30%的数据，n,m<=100；

对于100%的数据，n,m<=1000；

保证k<=(r-l+1)，序列中的数<=106。

import java.util.Scanner;

public class Main {

    //对数组array中下标start到end中的元素进行归并并排，求得该区间的降序排列

    public void mergeSort(int[] array, int start, int end) {

        if(end - start >= 1) {

            int[] leftArray = getHalfArray(array, start, end, 0);

            int[] rightArray = getHalfArray(array, start, end, 1);

            mergeSort(leftArray, 0, leftArray.length - 1);

            mergeSort(rightArray, 0, rightArray.length - 1);

            getMerge(array, start, leftArray, rightArray);

        }

    }

    //根据judge获取数组array区间start~end的一半元素

    public int[] getHalfArray(int[] array, int start, int end, int judge) {

        int[] half;

        int len = end - start + 1;

        if(judge == 0) {

            int length = len / 2;

            half = new int[length];

            for(int i = 0;i < length;i++)

                half[i] = array[start + i];

        } else {

            int length = len - len / 2;

            half = new int[length];

            for(int i = 0;i < length;i++) {

                half[i] = array[start + len / 2 + i];

            }

        }

        return half;

    }

    //合并数组array的左半边元素和右半边元素，返回降序排列

    public void getMerge(int[] array, int start, int[] leftArray, int[] rightArray) {

        int i = 0, j = 0;

        while(i < leftArray.length && j < rightArray.length) {

            if(leftArray[i] >= rightArray[j])

                array[start++] = leftArray[i++];

            else

                array[start++] = rightArray[j++];

        }

        while(i < leftArray.length) array[start++] = leftArray[i++];

        while(j < rightArray.length) array[start++] = rightArray[j++];

    }

    public void printResult(int[] array, int[][] query) {

        int[] result = new int[query.length];

        for(int i = 0;i < query.length;i++) {

            int[] tempArray = new int[array.length];  //此处获取array的克隆对象，要求地址也要改变。若直接赋值，两者地址是一样

            for(int j = 0;j < array.length;j++)

                tempArray[j] = array[j];

            int start = query[i][0];

            int end = query[i][1];

            int k = query[i][2];

            if(k < 0 || k > end - start + 1)   //防止k出界

                continue;

            mergeSort(tempArray, start - 1, end - 1);

            result[i] = tempArray[start - 1 + k - 1];

        }

        //输出结果

        for(int i = 0;i < result.length;i++)

            System.out.println(result[i]);

    }

    public static void main(String[] args) {

        Main test = new Main();

        Scanner in = new Scanner(System.in);

        int n = in.nextInt();

        int[] array = new int[n];

        for(int i = 0;i < array.length;i++)

            array[i] = in.nextInt();

        int m = in.nextInt();

        if(n > 1000 || m > 1000)

            return;

        int[][] query = new int[m][3];

        for(int i = 0;i < m;i++) {

            query[i][0] = in.nextInt();

            query[i][1] = in.nextInt();

            query[i][2] = in.nextInt();

        }

        test.printResult(array, query);

    }

}