Медиана отрезка

Дан массив, который не меняется. Для каждого запроса выведите медиану отрезка — элемент, стоящий на позиции $\lceil k/2 \rceil$ в отсортированном отрезке длины $k$.

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

Для каждого запроса выведите медиану отрезка на отдельной строке.