题目背景

小A的公司发年终奖了，年终奖是一个整数数组。当然，小A希望得到一些钱，而不是一个数组。

题目描述

小B喜欢数组，所以小A准备把数组卖给小B。经过磋商，他们约定，一个数组的价格是 $\max(a_1,a_2,…,a_n) \times \min(a_1,a_2,…,a_n) \times n$，其中 $a$ 是数组，$n$ 是数组长度。

小A打算卖给小B他的数组中所有的连续的子序列。你知道，小A的OI不好，所以他想请你帮他计算所有子序列的总价格。他只需要知道总价格最后 $9$ 位数字，因此你不需要担心数字太大。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个正整数 $a_1,a_2,…,a_n$。

输出格式

输出总价格最后 $9$ 位数字。

样例 #1

样例输入 #1

4
2 4 1 4

样例输出 #1

109

提示

对于 $30\%$ 的数据，$n \le 1000$。

对于 $100\%$ 的数据，$n \le 5 \times 10^5$，$a_i \le 10^8$。