NORMA2 - Norma


### 题目描述 你有一个长度为 $n$ 的序列,定义这个序列中每个区间的价值是 $$\operatorname{Cost}(i,j)=\min(A_{i}, \cdots, A_{j})\times \max(A_{i}, \cdots, A_{j})\times (j-i+1)$$ 其中,$i,j$ 是区间的两个端点。 现在请你求出给定序列所有区间的价值之和。 ### 输入 第 $1$ 行一个整数 $n$,表示这个序列有 $n$ 个数。 第 $2\sim n+1$ 行每行一个整数,第 $i+1$ 行的整数代表这个序列的第 $i$ 个数。 ### 输出 一行,一个整数。给定序列所有区间的价值之和。 ### 样例输入(与原题的样例不同) ``` 4 2 4 1 4 ``` ### 样例输出 ``` 109 ``` ### 数据范围 对于所有数据保证 $n \leq 5\times 10 ^ 5$,所有序列中的数 $A_{i}$ 满足 $A_{i} \leq 10 ^ 8$。


Mirko got an array of integers for his birthday from his grandmother Norma. As any other kid, he was hoping for some money, but got an array. Luckily, in his town there is a pawn shop that buys up arrays. The cost of an array of integers is **min** \* **max** \* **L** kunas, where **min** is the minimal integer in the array, **max** is the maximal and **L** is the array length. Mirko is going to sell a subsequence of consecutive numbers from his array. He calculated the average price of all such subsequences. In order to check his result, he wants you to do the same. He will be pleased with only the last 9 digits of the sum of all prices, so you don’t need to bother with large and real numbers.



The first line of input contains an integer N (1 Each of the following N lines contains a member of Mirko’s array. The members of the array will be integers from the interval \[1, 10 $ ^{8} $ \].


The first and only line of output must contain an integer, the last 9 digits of the required sum from the task. **You don’t need to output** the leading zeroes of that 9-digit integer.


输入样例 #1


输出样例 #1