Bessie is trying to sort an array of integers using her own sorting algorithm. She has a pile of N (1≤N≤2⋅105) integers a1,a2,…,aN (1≤ai≤1011) 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 ai, Bessie instructs that cow to nap for ai 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≤T≤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 a1,a2,…,aN, 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⋅105.
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,1011 for herself.
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.
SCORING:
Input 2: N≤16
Inputs 3-5: N≤150
Inputs 6-8: ∑N≤5000
Inputs 9-11: No additional constraints.
Problem credits: Suhas Nagar
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
