A. Разрушение башен
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Утёнок Кряк вернулся на родину и обнаружил $$$n$$$ башен, стоящих в ряд. Высота $$$i$$$-й башни равна $$$a_i$$$. Жаждая мести за уничтожение своей экосистемы, он поклялся причинить как можно больше разрушений с помощью своей лазерной пушки.

Утёнок Кряк произведёт операцию над каждой башней ровно один раз, в любом порядке по своему выбору. Операция над башней $$$i$$$ выглядит следующим образом:

  • Утёнок Кряк взбирается на вершину башни $$$i$$$ и стреляет лазером вправо, срезая первую более высокую башню, в которую он попадает, до высоты башни $$$i$$$.

    Формально, пусть $$$j$$$ — наименьший индекс такой, что $$$j \gt i$$$ и $$$a_j \gt a_i$$$, где $$$a_i$$$ и $$$a_j$$$ — текущие высоты башен. Если такой $$$j$$$ существует, то $$$a_j$$$ заменяется на $$$a_i$$$. В противном случае ничего не происходит.

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

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1\le n\le 100$$$) — количество башен.

Следующая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le 1000$$$) — высоты башен.

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

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

Пример
Входные данные
10
3
1 3 5
3
5 4 3
4
3 2 5 1
4
2 1 4 3
5
4 1 3 5 2
5
2 2 3 1 4
1
7
6
6 1 5 2 4 3
4
1 1 1 1
5
10 3 8 6 9
Выходные данные
3
12
8
5
8
8
7
11
4
22
Примечание

В первом наборе входных данных один из оптимальных порядков: $$$3,1,2$$$. Высоты изменяются следующим образом:

$$$$$$ [1,3,5]\to [1,3,5]\to [1,1,5]\to [1,1,1]. $$$$$$

Таким образом, итоговая сумма равна $$$1+1+1=3$$$.

Во втором наборе входных данных ни одна операция не может изменить ни одну башню. Для каждой башни справа нет более высокой башни. Поэтому итоговые высоты остаются $$$[5,4,3]$$$, и ответ равен $$$5+4+3=12$$$.

В третьем наборе входных данных один из оптимальных порядков: $$$4,1,3,2$$$. Высоты изменяются следующим образом:

$$$$$$ [3,2,5,1]\to [3,2,5,1]\to [3,2,3,1]\to [3,2,3,1]\to [3,2,2,1]. $$$$$$

Таким образом, итоговая сумма равна $$$3+2+2+1=8$$$.