Bessie пытается отсортировать массив целых чисел своим алгоритмом. У неё куча из $N$ чисел $a_1,a_2,\dots,a_N$, где $(1 \leq N \leq 2\cdot 10^5)$ и $(1 \leq a_i \leq 10^{11})$, которые она поместит в отдельный массив в отсортированном порядке. Она многократно находит минимум в куче, удаляет его и добавляет в конец массива. Поиск минимума в куче из $p$ чисел занимает $p$ секунд.

Farmer John поручил другим коровам помогать Bessie, но они ленивы, и она использует это. Она делит числа на свою кучу и кучу помощниц. Свою кучу обрабатывает обычным алгоритмом, а каждое число из второй отдаёт отдельной помощнице. Ферма велика, поэтому помощниц можно получить сколько угодно. Получив число $a_i$, помощница спит $a_i$ секунд и сразу после пробуждения добавляет его в конец массива. Если Bessie и помощница добавляют числа одновременно, число Bessie добавляется первым, поскольку она руководитель. Несколько помощниц с одинаковым числом одновременно добавляют его копии.

Помогите разделить числа так, чтобы итоговый массив был отсортирован, а время сортировки минимально.

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

Первая строка содержит число независимых тестовых случаев $T$ ($1\le T\le 10$).

Каждый случай имеет следующий формат:

Первая строка содержит количество чисел $N$ в массиве Bessie.

Следующая строка содержит сортируемые числа $a_1, a_2, \dots, a_N$. Одно число может встречаться несколько раз.

Сумма $N$ по всем случаям не превышает $2\cdot 10^5$.

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

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

Примеры

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

4
5
1 2 4 5 100000000000
5
17 53 4 33 44
4
3 5 5 5
6
2 5 100 1 4 5

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

6
15
5
6

Примечание

В первом примере Bessie может отдать $1,2$ помощницам, оставив $4,5,10^{11}$ себе.

Во втором примере лучше всего сортировать всё самой. Отдать $4$ помощнице, а остальное оставить себе — неподходящее разделение: Bessie добавит $17$ раньше, чем помощница добавит $4$.

В третьем примере все числа можно отдать помощницам.

В четвёртом примере можно отдать $1,4,5$ помощницам, оставив $2,5,100$ себе.

Подзадачи

• Вход 2: $N\le 16$
• Входы 3–5: $N\le 150$
• Входы 6–8: $\sum N\le 5000$
• Входы 9–11: без дополнительных ограничений.

Автор задачи: Suhas Nagar