Difference Array Solution Codeforces
You are given an arrayconsisting of non-negative integers. It is guaranteed that is sorted from small to large.
For each operation, we generate a new arrayfor . Then we sort from small to large, replace with , and decrease by .
After performingoperations, becomes . You need to output the only integer in array (that is to say, you need to output ).
Input Difference Array Solution Codeforces
The input consists of multiple test cases. The first line contains a single integer( ) — the number of test cases. The description of the test cases follows.
The first line of each test case contains one integer( ) — the length of the array .
The second line containsintegers ( ) — the array .
It is guaranteed that the sum ofover all test cases does not exceed , and the sum of over all test cases does not exceed .
Output Difference Array Solution Codeforces
For each test case, output the answer on a new line.
5 3 1 10 100 4 4 8 9 13 5 0 0 0 8 13 6 2 4 8 16 32 64 7 0 0 0 0 0 0 0
81 3 1 2 0
Note Difference Array Solution Codeforces
To simplify the notes, letdenote the array you get by sorting from small to large.
In the first test case,at first. After the first operation, . After the second operation, .
In the second test case,at first. After the first operation, . After the second operation, . After the last operation, .