K-ое число
Вы работаете на компанию МакроХард в отделе структуры данных. После неудачного решения предыдущей задаче о вставки ключей, Вас попросили написать новую структуру данных, позволяющую быстро находить k-ую порядковую статистику на указанном отрезке.
Задан массив a[1...n] различных целых чисел. Необходимо отвечать на вопросы Q(i, j, k) следующего вида: "Найти k-ое число на отрезке a[i ... j], если все числа на этом отрезке предварительно отсортировать".
Например, рассмотрим отрезок a = (1, 5, 2, 6, 3, 7, 4). Рассмотрим запрос Q(2, 5, 3). Отрезком a[2 ... 5] будет (5, 2, 6, 3). Отсортировав числа, получим (2, 3, 5, 6). Третьим элементом будет 5. Ответом на запрос будет 5.
Входные данные
Первая строка содержит размер массива n и количество запросов m (1 ≤ n ≤ 100000, 1 ≤ m ≤ 5000).
Вторая строка содержит n разных целых чисел, не превосходящих 10^9 по абсолютному значению - массив чисел, к которому будут ставиться запросы.
Следующие m строк содержат запросы, каждый из которых состоит из трех чисел: i, j и k (0 ≤ i ≤ j ≤ n, 0 ≤ k ≤ j - i + 1) и представляет собой запрос Q(i, j, k).
Выходные данные
Для каждого запроса вывести k-ое число в отсортированном отрезке a[i ... j].