AT_abc407_f [ABC407F] Sums of Sliding Window Maximum

You are given a sequence of non-negative integers $ A = (A_1,\dots,A_N) $ of length $ N $ . For each $ k = 1,\dots,N $ , solve the following problem: - $ A $ has $ N-k+1 $ (contiguous) subarrays of length $ k $ . Take the maximum of each of them, and output the sum of these maxima.

The input is given from Standard Input in the following format: > $ N $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

Output $ N $ lines. The $ i $ -th line ( $ 1 \le i \le N $ ) should contain the answer for $ k = i $ .

### Sample Explanation 1 For $ k = 1 $ , there are four subarrays of length $ k=1 $ : - $ (5) $ , whose maximum is $ 5 $ ; - $ (3) $ , whose maximum is $ 3 $ ; - $ (4) $ , whose maximum is $ 4 $ ; - $ (2) $ , whose maximum is $ 2 $ . The sum is $ 5 + 3 + 4 + 2 = 14 $ . For $ k = 2 $ , there are three subarrays of length $ k=2 $ : - $ (5,3) $ , whose maximum is $ 5 $ ; - $ (3,4) $ , whose maximum is $ 4 $ ; - $ (4,2) $ , whose maximum is $ 4 $ . The sum is $ 5 + 4 + 4 = 13 $ . For $ k = 3 $ , there are two subarrays of length $ k=3 $ : - $ (5,3,4) $ , whose maximum is $ 5 $ ; - $ (3,4,2) $ , whose maximum is $ 4 $ . The sum is $ 5 + 4 = 9 $ . For $ k = 4 $ , there is one subarray of length $ k=4 $ : - $ (5,3,4,2) $ , whose maximum is $ 5 $ . The sum is $ 5 $ . ### Constraints - $ 1 \le N \le 2 \times 10^{5} $ - $ 0 \le A_i \le 10^{7} $ ( $ 1 \le i \le N $ ) - All input values are integers.