The Minimum Number Of Moves

The Minimum Number Of Moves

Little chief has his own restaurant in the city. There are N workers there. Each worker has his own salary. The salary of the i-th worker equals to W_i (i = 1, 2, ..., N). Once, chief decided to equalize all workers, that is, he wants to make salaries of all workers to be equal. But for this goal he can use only one operation: choose some worker and increase by 1 salary of each worker, except the salary of the chosen worker. In other words, the chosen worker is the loser, who will be the only worker, whose salary will be not increased during this particular operation. But loser-worker can be different for different operations, of course. Chief can use this operation as many times as he wants. But he is a busy man. That's why he wants to minimize the total number of operations needed to equalize all workers. Your task is to find this number.

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains a single integer N denoting the number of workers. The second line contains N space-separated integers W₁, W₂, ..., W_N denoting the salaries of the workers.

Output

For each test case, output a single line containing the minimum number of operations needed to equalize all workers.

Constraints

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 100
• 0 ≤ W_i ≤ 10000 (10⁴)

Example

Input:
2
3
1 2 3
2
42 42

Output:
3
0

Explanation

Example Case 1. Chief can equalize all salaries in 3 turns:

Turn ID	IDs of involved workers	Salaries after the move
1	1 2	2 3 3
2	1 2	3 4 3
3	1 3	4 4 4

Problem Solving

1. This problem took me some time to grasp. Do not think otherwise but the issue here is that I did jump on solving the solution, however first I wanted to formally convince myself that a solution to this problem exists.
2. Turns out that no one on the editorial or discussion have answered this issue. How do I know that in any configuration of W there will exist a solution where are salaries will be equal after performing the mentioned operation multiple times. 
3. So to do that I thought of using induction, Clearly if f -> true when the solution to problem exists then f(1) is always true, because for 1 worker all salaries are already equal & number of operations are also = 0. 
4. Thinking about f(2), if there are only 2 workers and since this operation always increases the value therefore the min moves would be to make the salary of the lesser worker equal to the worker whose salary is more i.e (Max(W[])-Min(W[])) number of moves. and also that the solution does exists. 
5. So lets assume that f(k) -> true. with some X operations. 
6. If we can argue that f(k + 1)  is also true then we would conclusively prove that a solution to this problem exists for every k >0.
7. Now for f(k+1) out of k + 1 lets partition them in 2 groups of k say G1 and  1 say G2, such that the group G2 has only one element which is the max element of all k + 1 elements, 
8. Now the group G1 is solvable by induction hypothesis - (5) by X operations. 
9. That means that the after performing X operations in all k+1 elements where we always choose candidate for operation from group G1, the final value of G2 would be value of G2 elements + X. (since each operation will expand the G2 group by 1. 
10. Now the final configuration after X operations would be that all salaries in G1 group would be equal say equal to E and G2 group salary would be increased by X. 
11. Finally we can perform X - E operations by always selecting G2 candidate and so that G2 candidate never increases and the rest in  G1 which were equal already would all increase to be equal to G2. 
12. Therefore all salaries can be made equal. QED 
13. So I convinced myself that a problem can be solved. 
14. Now for the number of operations, also took sometime to ponder, If the only operation is increase all but one, that means that the minimum number of the set should dictate the number of operations. 
15. Doing sample examples would show that keeping max as the candidate and pulling up all the rest will yield the min number of operations. 
16. Now this is tricky to imagine but if you pull up your min to the successor on the min value, then we have a case just like in the proof, where we try to make all other equal and then finally we can just move all except for the one that is max. So we can try pulling up min to the next min in every iteration. 
17. This operation sequence will give us the min operations required. 
18. However instead of modelling this behavior, one can calculate how many operations does that mean. 
19. That means that in each iteration I make min equal to a next element therefore for every element this happens equal to the difference to the min value. 
20. Therefore E (0,n) (Wi - min(w)) is the answer. 

• For implementation 
• we can see that most variables are in int range and the summation would max to 10^4 * 100 = 10 ^ 6 which is also integer range. so no overflow requirements. 
• Next we see that we can find the summation and min elements in one scan of the input and the compute the answer so time can be O(1) and space also O(1).  
• No extra edge cases here. 
• The submission went successful here . 

Learning 

• Proof by induction was the best thing about this problem solving. The ability to convince oneself that yes there is a solution is great, also it provides insights to solve the actual problem.
• The problem can seem much easier if one thinks in a relative aspect. Since the only thing that matters is that all salaries become equal so the operation can also be thought of pushing one salary down each time instead of pulling all salaries except for one. In relative terms these are the same thing. 
• The relative aspect is great but to get the final salary, it becomes is difficult. 
• The final salary in the above approach is easy to think as min + number of total operations. (since in each operation the min have always increased, and the min was never a candidate to not increase the salary, the final = min + num of operations) 
• This problem was of cake walk difficulty, however it took me some time to ponder on the details. A lot of time compared to time requirements  of competitive programming. 
• This however should not sadden me, as my goal here is to learn and solve everything instead solve it fast. 
• Let's see what other problems have to offer. :)