桌上有 $N$ 個箱子排成一列,每個箱子的驚喜度分別為 $A_1, A_2, \dots, A_N$,小 K 隨意選擇一個連續區段的所有箱子(可以只有一個箱子)。接著小 K 要打開選擇的箱子,假設區間內箱子的驚喜度是 $A_L, A_{L+1}, \dots A_R$,定義開箱精彩度是 $\min(A_L, A_{L+1}, \dots, A_R)$。
小 K 總共有 $\frac{N(N+1)}{2}$ 種選擇方式,請你求出所有方式的開箱精彩度總和。
輸入第一行是一個整數 $N$,表示箱子數量。
接著一行是 $N$ 個空白分隔的整數 $A_1, A_2, \dots, A_N$ 表示每個箱子的驚喜度。
輸入保證 $1\le N\le 10^ 5$,$1\le A_i\le 10^ 9$。
輸出一個整數表示開箱精彩度總和。
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~1 | 範例測資 | 0 |
2 | 0~16 | 無額外限制 | 100 |