CF2030A A Gift From Orangutan

While exploring the jungle, you have bumped into a rare orangutan with a bow tie! You shake hands with the orangutan and offer him some food and water. In return... The orangutan has gifted you an array $ a $ of length $ n $ . Using $ a $ , you will construct two arrays $ b $ and $ c $ , both containing $ n $ elements, in the following manner: - $ b_i = \min(a_1, a_2, \ldots, a_i) $ for each $ 1 \leq i \leq n $ . - $ c_i = \max(a_1, a_2, \ldots, a_i) $ for each $ 1 \leq i \leq n $ . Define the score of $ a $ as $ \sum_{i=1}^n c_i - b_i $ (i.e. the sum of $ c_i - b_i $ over all $ 1 \leq i \leq n $ ). Before you calculate the score, you can shuffle the elements of $ a $ however you want. Find the maximum score that you can get if you shuffle the elements of $ a $ optimally.

The first line contains $ t $ ( $ 1 \leq t \leq 100 $ ) — the number of test cases. The first line of each test case contains an integer $ n $ ( $ 1 \leq n \leq 1000 $ ) — the number of elements in $ a $ . The following line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq 1000 $ ) — the elements of the array $ a $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 1000 $ .

For each test case, output the maximum score that you can get.

In the first test case, there is no other way to rearrange $ a $ . So, $ b = [69] $ and $ c = [69] $ . The only possible score is $ 69 - 69 = 0 $ . In the second test case, you can rearrange $ a $ as $ [7, 5, 6] $ . Here, $ b = [7, 5, 5] $ and $ c = [7, 7, 7] $ . The score in this case is $ (7 - 7) + (7 - 5) + (7 - 5) = 4 $ . It can be shown this is the maximum possible score.