2809 「COCI 2014.11.08」NORMA

译自 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),(3),(1,3)$。

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

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