e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

ADA University - March 7 - Segment Tree

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 (1n100000, 1m5000).

Другий рядок містить n різних цілих чисел, які не перевищують 109 за абсолютним значенням - масив чисел, до якого будуть задаватись запити.

Наступні m рядків містять запити, кожен з яких складається з трьох чисел: i, j та k (0ijn, 0kj - i + 1) і являє собою запит Q(i, j, k).

Вихідні дані

Для кожного запиту вивести k-те число у відсортованому відрізку a[i...j].

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
Вихідні дані #1
5
6
3

Пояснення: Великий об`єм вхідних даних, використовуйте c-стиль читання даних (scanf,printf), інакше буде Тайм Ліміт

Джерело 2004 NEERC, Northern Subregion, October 30, Problem K