先備知識： RMQ Problem(Range Minimum/Maximum Query)，區間最小/大值問題是一個很常見的問題。 簡單來說就是給定一個陣列A和Q個詢問，每次詢問A中某個區間的最大值/最小值。 這個問題使用線段樹可以達到預處理/詢問複雜度\(O(N)/O(logN)\)，而使用稀疏表可以達到\(O(NlogN)/O(1)\)。   給定一個陣列A，定義\(RMQ(l,r)\)表示\(A[l,r]\)中的最小值，請輸出 [ \sum_{i=1}^{N}\sum_{j=i}^{N} RMQ(i,j) ]

輸入格式

第一行為A的長度\(N(N \leq 200000)\) 第二行是A裡面的數字(絕對值 \(\leq 10^5\))。

輸出格式

[ \sum_{i=1}^{N}\sum_{j=i}^{N} RMQ(i,j) ]

範例輸入

5
1 2 3 4 5

範例輸出

35

提示

子題一(40%)：\(N \leq 2000\) 子題二(60%)：無其他限制。