题目描述

译自 COCI 2014.11.08 T6. NORMA

在 Mirko 生日那天，他收到了祖母送他的一个数列 $A$。Mirko 居住的小镇上有一户人家专门收购数列（什么人啊）。对于一个数列 $L$，它的价值 $v_L=\min{L_i}\times \max{L_i}\times \mathit{len}_L$（即数列的最小值，最大值与长度的积）。Mirko 计算了 $A$ 的所有子串的价值之和。
为了检查他的结果，你也要这么做。答案对 $10^9$ 取模。

输入格式

第一行一个正整数$N$。
接下来 $N$ 行，每行一个正整数 $a_i$，描述了 Mirko 的数列 $A$。

输出格式

一行代表所有子串的价值之和对 $10^9$ 取模的结果。

样例 1

input

2
1
3

output

16

所有子串分别为 $(1),(3),(1,3)$。

样例 2

input

4
2
4
1
4

output

109

所有子串分别为 $(2),(4),(1),(4),(2,4),(4,1),(1,4),(2,4,1),(4,1,4),(2,4,1,4)$。

样例 3

input

6
8
1
3
9
7
4

output

1042

数据范围与提示

对于 $40\%$ 的数据，$N<5000$；
对于 $100\%$ 的数据，$1\leq N \leq 5\times 10^5,1\leq a_i \leq 10^8$。