Республиканская олимпиада по информатике 2019 года за 9 класс | Казахстанские олимпиады

Задача C. Поиск медианы

Дан массив чисел $a$ длинны $n$ и $q$ запросов.

Каждый из запросов описывается числами $l$ и $r$. Для каждого из запросов нужно найти, какой будет медиана в массиве, если удалить числа из массива от $l$ до $r$.

Формат входного файла

В первой строке входных данных подаются 2 числа $n, q$ $(1 <= n, q <= 10^6)$ — количество чисел в массиве и количество запросов.

Во второй строке входных данных подаются $n$ целых чисел $a_i$ $(1 <= a_i <= 10^9)$ — $i$-й элемент массива $a$.

В последующих $q$ строках подаются по два целых числа $l, r$ $(1 <= l <= r <= n)$ — границы удаляемого отрезка. Гарантируется что в оставшемся массиве будет хотя бы один элемент.

Формат выходного файла

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

Примеры

Вход

5 5
1 2 1 4 9
2 4
1 1
4 5
3 4
1 3

Выход

1
2
1
2
4