Mirko 从他的祖母 Norma 那里收到了一个整数数组作为生日礼物。像其他孩子一样，他本希望能收到一些零花钱，但却只得到了一个数组。幸运的是，他所在的城镇有一家收购数组的典当行。一个整数数组的价格为 $\min \cdot \max \cdot L$ 库纳（kunas），其中 $\min$ 是数组中的最小值，$\max$ 是最大值，$L$ 是数组的长度。Mirko 打算卖掉他数组中的一段连续子数组。他计算了所有这些连续子数组的平均价格。

为了验证他的计算结果，他希望你也做同样的事情。不过，他只需要所有价格之和的最后 9 位数字，因此你不需要为大数和实数而烦恼。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 500\,000$)。

接下来的 $N$ 行，每行包含一个 Mirko 数组中的元素。数组中的元素均为区间 $[1, 10^8]$ 内的整数。

输出格式

输出第一行且仅一行，包含一个整数，即所求价格总和的最后 9 位数字。你不需要输出该 9 位整数的前导零。

子任务

在占总分 $40\%$ 的测试数据中，满足 $N < 5000$。

样例

输入样例 1

2
1
3

输出样例 1

16

输入样例 2

4
2
4
1
4

输出样例 2

109

输入样例 3

6
8
1
3
9
7
4

输出样例 3

1042

说明

第一个样例的解释： 数组由两个整数 $1$ 和 $3$ 组成。Mirko 可以出售的可能连续子数组为 $(1)$、$(3)$ 和 $(1, 3)$，它们的价格分别为 $1$、$9$ 和 $6$，总和为 $16$。

第二个样例的解释： Mirko 可以出售的可能连续子数组为 $(2)$、$(4)$、$(1)$、$(4)$、$(2, 4)$、$(4, 1)$、$(1, 4)$、$(2, 4, 1)$、$(4, 1, 4)$ 和 $(2, 4, 1, 4)$。它们的价格分别为 $4$、$16$、$1$、$16$、$16$、$8$、$8$、$12$、$12$ 和 $16$，总和为 $109$。