Problem 3. Nap Sort

USACO 2024 January Contest, Gold

Bessie is trying to sort an array of integers using her own sorting algorithm. She has a pile of $N$ $(1 \leq N \leq 2\cdot 10^5)$ integers $a_1,a_2,\dots,a_N$ $(1 \leq a_i \leq 10^{11})$ that she will put in a separate array in sorted order. She repeatedly finds the minimum integer in her pile, removes it, and adds it to the end of the array. It takes Bessie $p$ seconds to find the minimum integer in a pile of $p$ integers.

Farmer John instructed some of the other cows in the farm to help Bessie with her task, but they are quite lazy, so Bessie uses that to her advantage. She divides the integers into two piles: Bessie pile and Helper pile. For every integer in Bessie's pile, she performs her algorithm as normal. For every integer in the helper pile, she assigns it to a different helper cow. Farmer John has a large farm, so Bessie can get as many helper cows as she wants. If a helper receives the integer $a_i$, Bessie instructs that cow to nap for $a_i$ seconds, and add their integer to the end of the array immediately when they wake up. If Bessie and a helper add an integer to the array at the same time, Bessie's integer will get added first since she is the leader. If more than one helper gets assigned the same integer, they will add copies of that integer to the array at the same time.

Help Bessie divide her integers so that the final array is sorted and the time it takes to sort the array is minimized.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains $T$, the number of independent test cases ($1\le T\le 10$).

Each test case is formatted as follows:

The first line of each test case contains the number of integers $N$ in Bessie's array.

The next line of each test case contains $a_1, a_2, \dots, a_N$, the integers that Bessie is sorting. The same integer may appear multiple times.

It is guaranteed that the sum of $N$ over all tests does not exceed $2\cdot 10^5$.

OUTPUT FORMAT (print output to the terminal / stdout):

For each test case, output the minimum time to sort the array on a new line, if Bessie divides her integers optimally.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

6
15
5
6

In the first example, Bessie can assign $1,2$ to helpers and leave $4,5,10^{11}$ for herself.

Time | Event
-----+----------------------
1    | Helper adds 1
2    | Helper adds 2
3    | Bessie adds 4
5    | Bessie adds 5
6    | Bessie adds 10^{11}

In the second example, the best Bessie can do is sort everything by herself. One division that does not work is for Bessie to assign $4$ to a helper and the rest to herself because Bessie will end up adding $17$ to the array before the helper adds $4$ to the array.

In the third example, Bessie can assign all the integers to helpers.

In the fourth example, Bessie can assign $1,4,5$ to helpers and leave $2,5,100$ to herself.

Time | Event
-----+------------------
1    | Helper adds 1
3    | Bessie adds 2
4    | Helper adds 4
5    | Bessie adds 5
5    | Helper adds 5
6    | Bessie adds 100

SCORING: Input 2: $N\le 16$Inputs 3-5: $N\le 150$Inputs 6-8: $\sum N\le 5000$Inputs 9-11: No additional constraints.

Problem credits: Suhas Nagar