{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"# 翻译在下方"}},{"title":"","value":{"format":"MD","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003eYou are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment. \n\u003cbr\u003eThat is, given an array a[1...n] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: \"What would be the k-th number in a[i...j] segment, if this segment was sorted?\" \n\u003cbr\u003eFor example, consider the array a \u003d (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2...5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5. \u003c/div\u003e"}},{"title":"Input","value":{"format":"MD","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003eThe first line of the input file contains n --- the size of the array, and m --- the number of questions to answer (1 \u0026lt;\u003d n \u0026lt;\u003d 100 000, 1 \u0026lt;\u003d m \u0026lt;\u003d 5 000). \n\u003cbr\u003eThe second line contains n different integer numbers not exceeding 10\u003csup\u003e9\u003c/sup\u003e by their absolute values --- the array for which the answers should be given. \n\u003cbr\u003eThe following m lines contain question descriptions, each description consists of three numbers: i, j, and k (1 \u0026lt;\u003d i \u0026lt;\u003d j \u0026lt;\u003d n, 1 \u0026lt;\u003d k \u0026lt;\u003d j - i + 1) and represents the question Q(i, j, k). \u003c/div\u003e"}},{"title":"Output","value":{"format":"MD","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003eFor each question output the answer to it --- the k-th number in sorted a[i...j] segment. \u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"MD","content":"\u003cpre class\u003d\"sio\"\u003e7 3\n1 5 2 6 3 7 4\n2 5 3\n4 4 1\n1 7 3\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"MD","content":"\u003cpre class\u003d\"sio\"\u003e5\n6\n3\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"MD","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003eThis problem has huge input,so please use c-style input(scanf,printf),or you may got time limit exceed.\u003c/div\u003e"}},{"title":"翻译","value":{"format":"MD","content":"### 题目描述:\n给定一个数组$a[1…n]$,数组元素各不相同,你的程序要对每次查询$Q(i,j,k)$作出回答,其中$Q(i,j,k)$的含义为在数组$a[i…j]$中第$k$大的数字。\n例如,给出数组$a\u003d(1, 5, 2, 6, 3, 7, 4)$。查询语句为$Q(2,5,3)$,即从$(5,2,6,3)$中找出第$3$大的元素,将之排序得到$(2,3,5,6)$,故第三大的数字是$5$,所以这次查询的结果应当为$5$。\n\n### 输入格式:\n数据第1行有两个数字$N$与$M$,分别表示数组元素的个数与查询次数$(1\u003c\u003dn\u003c\u003d100000,1\u003c\u003dm\u003c\u003d5000)$\n第$2$行有$N$个数字,表示数组中的各元素,数组中各元素互不相同,并且每个数字的绝对值不超过$10^9$\n接下来的$m$行,每行包含$3$个数字$i,j,k,(1\u003c\u003di\u003c\u003dj\u003c\u003dn,1\u003c\u003dk\u003c\u003dj-i+1)$,表示一次查询$Q(i,j,k)$\n\n### 输出格式:\n对于每次查询,输出查询结果,即$a[i…j]$中第$k$大的数字,每个结果占一行\n\n### 样例输入 #1:\n```text\n7 3\n1 5 2 6 3 7 4\n2 5 3\n4 4 1\n1 7 3\n```\n\n### 样例输出 #1:\n```text\n5\n6\n3\n```\n\n### 说明与提示:\n输入数据较多,请使用C语言风格的输入输出语句\n\n```\nscanf(),printf()\n\n```\n否则可能发生 $Time Limit Exceed$."}}]}