L. Катая по величине на отрезке

Дан массив, который не меняется. Для каждого запроса $(l, r, k)$ выведите $k$-й по возрастанию элемент отрезка $[l, r]$.

Дерево слияний из предыдущей задачи это тоже умеет — двоичным поиском по ответу поверх запроса «сколько меньше», за $O(\log^3 n)$. Здесь разберём способ за один логарифм.

В первой строке $n$ и $q$ ($1 \le n, q \le 10^5$). Во второй — $n$ чисел $a_i$ ($0 \le a_i \le 10^9$). Далее $q$ строк по три числа $l$, $r$, $k$ ($1 \le l \le r \le n$, $1 \le k \le r - l + 1$).

Для каждого запроса выведите $k$-й по возрастанию элемент отрезка на отдельной строке.