{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"You 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. \r\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?\" \r\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. "}},{"title":"Input","value":{"format":"HTML","content":"The 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). \r\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. \r\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). "}},{"title":"Output","value":{"format":"HTML","content":"For each question output the answer to it --- the k-th number in sorted a[i...j] segment. "}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e7 3\r\n1 5 2 6 3 7 4\r\n2 5 3\r\n4 4 1\r\n1 7 3\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\r\n6\r\n3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"This problem has huge input,so please use c-style input(scanf,printf),or you may got time limit exceed."}}]}