Задача I. Kth.
Имя входного файла: stdin
Имя выходного файла: stdout
Максимальное время работы на одном тесте: 1 секунды
Максимальный объем используемой памяти: 64 мегабайта
Найти K-тое по величине число на отрезке.
Формат входных данных:
Первая строка входных данных содержит число N (1 ≤ N ≤ 100 000).
Во второй строке через пробел следуют N целых чисел от 0 до 2 000 000 000.
В треьей строке содержится число M - количество запросов(1 ≤ M ≤ 100).
В четвертой и следующих строках находятся запросы - каждый запрос представляет собой 3 целых числа li, ri, ki (1 ≤ li ≤ ri ≤ N, ki ≤ ri - li +1 )
Формат выходных данных:
Требуется на каждый запрос вывести единственное число, которое будет ki-м на отрезке с li по ri
Пример
| Пример ввода | Пример вывода |
4
1 2 3 0
2
1 4 1
2 3 2
|
0
3
|