CF2185B Prefix Max

You are given an array of $ n $ integers $ a_1, a_2, \ldots, a_n $ . The value of an array is the sum of the maximums of each prefix of the array. More formally, the value of an array $ a $ is $ \sum_{i=1} ^{n} \operatorname{max}(a_1, \ldots, a_i) $ . For example, the value of the array \[ $ 1, 2, 1 $ \] is $ \operatorname{max}(1) + \operatorname{max}(1, 2) + \operatorname{max}(1, 2, 1) = 1 + 2 + 2 = 5 $ . You can choose two indices $ i $ and $ j $ and swap elements $ a_i $ and $ a_j $ ; this operation can be applied at most one time. Find the maximum possible value of the array $ a $ after at most one operation.

The first line of the input contains a single integer $ t $ ( $ 1 \leq t \leq 100 $ ) — the number of test cases. The first line of each test case contains a single integer $ n $ ( $ 2 \le n \le 50 $ ) — the length of the array $ a $ . The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^4 $ ) — the array $ a $ .

For each test case, output the maximum possible value of the array $ a $ after the swap has been performed.

For the first test case, we can swap $ a_1 $ with $ a_4 $ to get the array \[ $ 5, 1, 4, 2, 3 $ \], which has a value of $ \operatorname{max}(5) + \operatorname{max}(5, 1) + \operatorname{max}(5, 1, 4) + \operatorname{max}(5, 1, 4, 2) + \operatorname{max}(5, 1, 4, 2, 3) = 25 $ . For the second test case, the current value of the array is $ \operatorname{max}(5) + \operatorname{max}(5, 1) = 10 $ . If we were to swap $ a_1 $ and $ a_2 $ , $ a $ would be equal to \[ $ 1, 5 $ \], which has a value of $ \operatorname{max}(1) + \operatorname{max}(1, 5) = 6 $ , meaning the best option is to not perform a swap.