В системе учёта хранится список из n товарных позиций. Для каждой позиции известна её прибыль — целое число, которое может быть как положительным, так и отрицательным.

Система должна быстро отвечать на запросы вида: какую суммарную выручку дадут k самых прибыльных позиций?

Для каждого запроса по числу k требуется вывести сумму k наибольших значений прибыли среди всех позиций.

Входные данные

Первая строка содержит целое число n — количество позиций.

Вторая строка содержит n целых чисел a_i — прибыли позиций.

Третья строка содержит целое число q — количество запросов.

В следующих q строках записано по одному целому числу k — сколько самых прибыльных позиций нужно учесть.

Выходные данные

Для каждого запроса выведите в отдельной строке сумму k наибольших прибылей.

Ответы могут не помещаться в 32-битный целочисленный тип.

Ограничения

1 <= n <= 2 * 10^5

-10^9 <= a_i <= 10^9

1 <= q <= 2 * 10^5

1 <= k <= n

Примеры

Пример 1

Входные данные

1
5
1
1

Выходные данные

5

Пример 2

Входные данные

5
5 -2 7 0 -9
5
1
2
3
4
5

Выходные данные

7
12
12
10
1