AT_abc407_f [ABC407F] Sums of Sliding Window Maximum

長さ $ N $ の非負整数列 $ A = (A_1, \dots, A_N) $ が与えられます。 $ k = 1, \dots, N $ について、次の問題を解いてください。 - $ A $ の連続部分列のうち長さが $ k $ のものは $ N-k+1 $ 個ある。それぞれの連続部分列について最大値を求めたとき、それらの合計を求めよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

$ N $ 行出力せよ。 $ i $ 行目 ( $ 1 \leq i \leq N $ ) には、 $ k = i $ に対する答えを出力せよ。

### Sample Explanation 1 $ k = 1 $ の場合、長さ $ k=1 $ の連続部分列は $ 4 $ 個あり、それぞれについて - $ (5) $ の最大値は $ 5 $ - $ (3) $ の最大値は $ 3 $ - $ (4) $ の最大値は $ 4 $ - $ (2) $ の最大値は $ 2 $ となり、これらの合計は $ 5+3+4+2 = 14 $ です。 $ k = 2 $ の場合、長さ $ k=2 $ の連続部分列は $ 3 $ 個あります。それぞれについて - $ (5,3) $ の最大値は $ 5 $ - $ (3,4) $ の最大値は $ 4 $ - $ (4,2) $ の最大値は $ 4 $ となり、これらの合計は $ 5+4+4 = 13 $ です。 $ k = 3 $ の場合、長さ $ k=3 $ の連続部分列は $ 2 $ 個あります。それぞれについて - $ (5,3,4) $ の最大値は $ 5 $ - $ (3,4,2) $ の最大値は $ 4 $ となり、これらの合計は $ 5+4 = 9 $ です。 $ k = 4 $ の場合、長さ $ k=4 $ の連続部分列は $ 1 $ 個あります。それぞれについて - $ (5,3,4,2) $ の最大値は $ 5 $ となり、これらの合計は $ 5 $ です。 ### Constraints - $ 1 \leq N \leq 2 \times 10^5 $ - $ 0 \leq A_i \leq 10^7 $ ( $ 1 \leq i \leq N $ ) - 入力はすべて整数である。