Задача №1817. k-я порядковая статистика
Батальон солдат вышел на построение. Все военные стали в один ряд и пересчитались: первый, второй, третий, ..., \(N\)-й. Каждый из них держит в руках бумажку с результатом своего тестирования IQ. Как известно, результатом тестирования IQ является число от 1 до \(10^9\). Так как солдатам было запрещено списывать, то результаты у всех различные.
Периодически к батальону подходит личный секретарь генерала Маши, делает запрос: «Если всех солдат с \(i\)-го по \(j\)-го упорядочить по результату теста, то кто из них окажется среди этих солдат на \(k\)-м месте?» — и быстро требует ответ. При этом Маша считает что \(i\)-й солдат имеет номер \(1\), \(i + 1\) имеет номер \(2\), ..., \(j\) имеет номер \(j - i + 1\). Большая просьба — решите эту задачу.
В первой строке входного файла содержится число \(1 \le N \le 5000\) — количество человек. Во второй строке содержатся эти \(N\) чисел, разделённые пробелами. В третьей строке содержится число \(1 \le M \le 10^6\) — количество запросов. И последние \(M\) строк содержат запросы в формате «i j k». Гарантируется, что запросы корректны, то есть \(1 \le i \le j \le N\) и на отрезке от \(i\)-го до \(j\)-го элемента включительно есть хотя бы \(k\) элементов.
На каждый запрос выведите единственное число — ответ на запрос.
5 1 3 2 4 5 3 1 3 2 1 5 1 1 5 2
3 1 3