NORMA2  Norma
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 * max * 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
The first line of input contains an integer N (1 ≤ N ≤ 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
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 9digit integer.
Example
Input: 2
1
3
Output: 16
Input:
4
2
4
1
4
Output:
109
Input:
6
8
1
3
9
7
4
Output:
1042
hide comments
nimphy:
20180520 10:58:07
cdq! 

nimphy:
20180519 05:49:14
uhu，How to solve it！ 

Szymon:
20150429 12:01:45
finally... mod 10^9 everywhere huhhh Last edit: 20150429 15:51:28 

Szymon:
20150428 21:12:21
nvm Last edit: 20150429 15:34:02 

chamini2:
20150216 07:14:24
Can you explain the first two examples? I'm not understanding what's the expected answer.


Basudeb Mandal:
20150115 13:28:53
Got it down to O(N^2), but now wrong answer on test 20 :( Will keep trying :) Last edit: 20150115 13:34:04 

Basudeb Mandal:
20150111 17:25:59
TLE on 20th test. Something's not right. :/

Added by:  Ivan Katanic 
Date:  20150109 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 JSMONKEY 
Resource:  COCI 14/15 Round 2 