题目描述

在 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

输入

2
1
3

输出

16

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

样例 2

输入

4
2
4
1
4

输出

109

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

样例 3

输入

6
8
1
3
9
7
4

输出

1042

数据范围与提示

对于 $40$ 的数据，$N<5000$；

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