CF1299C Water Balance

There are $ n $ water tanks in a row, $ i $ -th of them contains $ a_i $ liters of water. The tanks are numbered from $ 1 $ to $ n $ from left to right. You can perform the following operation: choose some subsegment $ [l, r] $ ( $ 1\le l \le r \le n $ ), and redistribute water in tanks $ l, l+1, \dots, r $ evenly. In other words, replace each of $ a_l, a_{l+1}, \dots, a_r $ by $ \frac{a_l + a_{l+1} + \dots + a_r}{r-l+1} $ . For example, if for volumes $ [1, 3, 6, 7] $ you choose $ l = 2, r = 3 $ , new volumes of water will be $ [1, 4.5, 4.5, 7] $ . You can perform this operation any number of times. What is the lexicographically smallest sequence of volumes of water that you can achieve? As a reminder: A sequence $ a $ is lexicographically smaller than a sequence $ b $ of the same length if and only if the following holds: in the first (leftmost) position where $ a $ and $ b $ differ, the sequence $ a $ has a smaller element than the corresponding element in $ b $ .

N/A

N/A

In the first sample, you can get the sequence by applying the operation for subsegment $ [1, 3] $ . In the second sample, you can't get any lexicographically smaller sequence.