k-я по величине зарплата без полной сортировки

Дан массив зарплат и q запросов: для каждого k выведите k-ю по возрастанию зарплату (как если бы массив отсортировали, нумерация с 1). Запросы независимы.

Используйте std::nth_element: для одного запроса он работает в среднем за O(n).

Ввод: n (1 ≤ n ≤ 4000), массив, затем q (1 ≤ q ≤ 200) и q чисел k (1 ≤ k ≤ n). |aᵢ| ≤ 10⁹.

Вывод: ответы через пробел.

Пример 1

Ввод:

5
30 10 50 20 40
3
1 3 5

Вывод:

10 30 50

Пример 2

Ввод:

1
-7
1
1

Вывод:

-7