2022: [USACO 2024 January Contest Gold] Problem 3. Nap Sort

Bessie is trying to sort an array of integers using her own sorting algorithm. She has a pile of $N$ $(1\le N\le 2\cdot {10}^5)$ integers $a_1,a_2,\dots ,a_N$
$(1\le a_i\le {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.

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$.

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

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

6
15
5
6