eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

K-те число (Easy)

K-те число (Easy)

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Ви працюєте на компанію МакроХард у відділі структури даних. Після невдалого розв'язання попередньої задачі про вставки ключів, Вас попросили написати нову структуру даних, яка дозволяє швидко знаходити 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 (1n, m100).

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

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

Вихідні дані

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

Приклад

Вхідні дані #1
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
Вихідні дані #1
5
6
3
Автор Andrew Stankevich