{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"Вы работаете в компании Macrohard в отделе структур данных. После неудачного выполнения предыдущей задачи по вставке ключа вам было поручено написать новую структуру данных, которая смогла бы быстро возвращать k-ый порядковую статистику в сегменте массива.\n\u003cbr\u003e\nЭто означает, что при заданном массиве a[1...n] различных целых чисел ваша программа должна отвечать на серию вопросов Q(i, j, k) в форме: \"Какое будет k-ое число в сегменте a[i...j], если этот сегмент был отсортирован?\"\n\u003cbr\u003e\nНапример, рассмотрим массив a \u003d (1, 5, 2, 6, 3, 7, 4). Пусть вопрос будет Q(2, 5, 3). Сегмент a[2...5] равен (5, 2, 6, 3). Если мы отсортируем этот сегмент, мы получим (2, 3, 5, 6), третье число равно 5, и, следовательно, ответом на вопрос будет 5."}},{"title":"Input","value":{"format":"HTML","content":"Первая строка входного файла содержит n - размер массива, и m - количество вопросов для ответа (1 \u003c\u003d n \u003c\u003d 100 000, 1 \u003c\u003d m \u003c\u003d 5 000).\n\u003cbr\u003e\nВторая строка содержит n различных целых чисел, не превышающих 10\u003csup\u003e9\u003c/sup\u003e по их абсолютным значениям - массив, для которого должны быть даны ответы.\n\u003cbr\u003e\nСледующие m строк содержат описания вопросов, каждое описание состоит из трех чисел: i, j и k (1 \u003c\u003d i \u003c\u003d j \u003c\u003d n, 1 \u003c\u003d k \u003c\u003d j - i + 1) и представляет вопрос Q(i, j, k)."}},{"title":"Output","value":{"format":"HTML","content":"Для каждого вопроса выведите ответ на него - k-ое число в отсортированном сегменте a[i...j]."}},{"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"}},{"title":"Hint","value":{"format":"HTML","content":"У этой задачи огромный входной объем, поэтому используйте ввод в стиле си (scanf, printf), иначе можете получить превышение времени выполнения."}}]}