402817: GYM100889 A A Beautiful Array
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
A. A Beautiful Arraytime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output![](https://espresso.codeforces.com/3c8a96a29eb94616e75638c3293507b3070ddbc1.png)
where
is integer division.Input
Little Tinu is a handsome kid and likes only beautiful things. He has an array and wants its most beautiful permutation. The beauty of a 1-indexed array A is defined as:
![](https://espresso.codeforces.com/3c8a96a29eb94616e75638c3293507b3070ddbc1.png)
![](https://espresso.codeforces.com/a64c1b2df604f8cfa9acf6716a3cc1424488361e.png)
The first line contains T(1 ≤ T ≤ 10), the number of test cases. Every test case contains 2 lines. First line has an integer N(1 ≤ N ≤ 103), the size of the array A. Second line contains the array A as space separated integers(0 ≤ Ai ≤ 106).
OutputOutput for each test case, the maximum beauty of any permutation of the array A.
ExampleInput
2Output
3
3 2 1
4
1 40 70 40
2Note
69
Sample test case 1:
There are 6 permutations possible:
Beauty = 2
Beauty = 1
Beauty = 1
Beauty = - 1
Beauty = - 1
Beauty = - 2
Maximum of all beauties is 2.
Sample test case 2:
The best permutation is [1, 40, 70, 40] where beauty is 69.