Mirko got an array of integers for his birthday from his grandmother Norma. As any other kid, he was hoping for some money, but got an array. Luckily, in his town there is a pawn shop that buys up arrays. The cost of an array of integers is ~min \times max \times L~ kunas, where ~min~ is the minimal integer in the array, ~max~ is the maximal and ~L~ is the array length. Mirko is going to sell a subsequence of consecutive numbers from his array. He calculated the average price of all such subsequences.

In order to check his result, he wants you to do the same. He will be pleased with only the last 9 digits of the sum of all prices, so you don't need to bother with large and real numbers.

Input Specification

The first line of input contains an integer ~N~ ~(1 \le N \le 500\,000)~.
Each of the following ~N~ lines contains a member of Mirko's array. The members of the array will be integers from the interval ~[1,10^8]~.

Output Specification

The first and only line of output must contain an integer, the last 9 digits of the required sum from the task. You don't need to output the leading zeroes of that 9-digit number.

Scoring

In test cases worth 40% of total points, it will hold ~N < 5\,000~.

Sample Input 1

2
1
3

Sample Output 1

16

Explanation for Sample 1

The array consists of two integers, 1 and 3. The possible subsequences Mirko can sell are ~(1)~, ~(3)~ and ~(1,3)~, their prices being 1, 9 and 6, respectively, which is 16 summed up.

Sample Input 2

4
2
4
1
4

Sample Output 2

109

Explanation for Sample 2

The possible subsequences Mirko can sell are ~(2)~, ~(4)~, ~(1)~, ~(4)~, ~(2,4)~, ~(4,1)~, ~(1,4)~, ~(2,4,1)~, ~(4,1,4)~ and ~(2,4,1,4)~. Their prices are 4, 16, 1, 16, 16, 8, 8, 12, 12 and 16, respectively, which is 109 summed up.

Sample Input 3

6
8
1
3
9
7
4

Sample Output 3

1042