CF2124G Maximise Sum

This problem differs from problem B. In this problem, you must output the maximum sum of prefix minimums over all operations that cost at least $ x $ for each integer $ x $ from $ 0 $ to $ n-1 $ . You are given an array $ a $ of length $ n $ , with elements satisfying $ \boldsymbol{0 \le a_i \le n} $ . You can perform the following operation at most once: - Choose two indices $ i $ and $ j $ such that $ i < j $ . Set $ a_i := a_i + a_j $ . Then, set $ a_j = 0 $ . Let the cost of one operation be the value of $ j-i $ . The cost of not performing an operation is $ 0 $ . For each integer $ x $ from $ 0 $ to $ n-1 $ inclusive, output the maximum possible value of $ \min(a_1) + \min(a_1,a_2) + \ldots + \min(a_1, a_2, \ldots, a_n) $ over all possible operations that have a cost of at least $ x $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains an integer $ n $ ( $ 2 \leq n \leq 10^6 $ ) — the length of $ a $ . The following line contains $ n $ space-separated integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le n $ ) — denoting the array $ a $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^6 $ .

For each test case, output $ n $ integers on a new line: the $ i $ -th integer denoting the maximum answer over all operations that have a cost of at least $ i-1 $ .

Let's analyze the fifth test case: - $ x=0,1,2 $ : the optimal operation is $ i=2 $ and $ j=4 $ , which has a cost of $ 2 $ . The array $ a $ becomes $ [4,4,3,0,1] $ , which has a score of $ 11 $ . - $ x=3 $ : the optimal operation is $ i=2 $ and $ j=5 $ , which has a cost of $ 3 $ . The array $ a $ becomes $ [4,2,3,3,0] $ , which has a score of $ 10 $ . - $ x=4 $ : the optimal (and only) operation is $ i=1 $ and $ j=5 $ , which has a cost of $ 4 $ . The array $ a $ becomes $ [5,1,3,3,0] $ , which has a score of $ 8 $ .