{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\r\n\u003ctable class\u003d\"problems\" width\u003d\"100%\"\u003e\u003ctbody\u003e\u003ctr class\u003d\"navigation\"\u003e\r\n\u003ctd width\u003d\"50%\"\u003e\u003ca href\u003d\"https://www.spoj.com/problems/MKTHNUM/en/\"\u003eEnglish\u003c/a\u003e\u003c/td\u003e \r\n\u003ctd width\u003d\"50%\"\u003e\u003ca href\u003d\"https://www.spoj.com/problems/MKTHNUM/vn/\"\u003eVietnamese\u003c/a\u003e\u003c/td\u003e \r\n\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\r\n\r\n\r\n\u003cp\u003e \u003c/p\u003e\r\n\u003cp\u003eYou are working for Macrohard company in data structures department. After\r\nfailing your previous task about key insertion you were asked to write a\r\nnew data structure that would be able to return quickly k-th order statistics\r\nin the array segment.\u003c/p\u003e\r\n\u003cp\u003eThat is, given an array a[1 ... n] of different integer numbers, your\r\nprogram must answer a series of questions Q(i, j, k) in the form: \"What would\r\nbe the k-th number in a[i ... j] segment, if this segment was sorted?\"\u003c/p\u003e\r\n\u003cp\u003eFor example, consider the array a \u003d (1, 5, 2, 6, 3, 7, 4). Let the question\r\nbe Q(2, 5, 3). The segment a[2 ... 5] is (5, 2, 6, 3). If we sort this\r\nsegment, we get (2, 3, 5, 6), the third number is 5, and therefore the\r\nanswer to the question is 5.\u003c/p\u003e\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eThe first line of the input contains n — the size of the array, and m —\r\nthe number of questions to answer (1 ≤ n ≤ 100000, 1 ≤ m ≤ 5000).\u003c/p\u003e\r\n\u003cp\u003eThe second line contains n different integer numbers not exceeding 10^9\r\nby their absolute values — the array for which the answers should be given.\u003c/p\u003e\r\n\u003cp\u003eThe following m lines contain question descriptions, each description consists\r\nof three numbers: i, j, and k (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ j - i + 1) and\r\nrepresents the question Q(i, j, k).\u003c/p\u003e\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eFor each question output the answer to it — the k-th number in sorted\r\na[i ... j] segment.\u003c/p\u003e\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cdiv\u003e\u003ctable class\u003d\"vjudge_sample\"\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\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\r\n6\r\n3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\r\n\r\n\u003cp\u003eNote: a naive solution will not work!!!\u003c/p\u003e\r\n\r\n\r\n \r\n\u003c/div\u003e"}}]}