DIFERENC - DIFERENCIJA

Mirko discovered what Slavko did in previous task, and decided to deal with something completely opposite to tables of letters: sequences of numbers.

Let’s define a value of a sequence as the difference between the largest and the smallest number within that sequence. For example, value of sequence (3, 1, 7, 2) is 6, and value of (42, 42) is 0.

Find the sum of values of all subsequences of consecutive elements of a given sequence.

Input

The first line of input contains a single integer N (2 ≤ N ≤ 300 000), number of elements of the sequence.

Next N lines contain elements of the sequence. Each element is a positive integer not greater than 100 000 000.

Output

The first and only line of output must contain the requested sum.

Example

Input:
3
1
2
3

output:
4
Input:
4
7
5
7
5

Output:
12
Input:
4
3
1
7
2

Output:
31

Added by:islam
Date:2012-02-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:COCI 2010/2011 Contest 3 by Adrian Satja Kurdija

hide comments
2013-02-03 16:23:39 (Tjandra Satria Gunawan)(曾毅昆)
@Francky: 100% true :-) even it's possible to find all answers (but require thousand of guessing, ans can be more than 10^18) But imho there're other weakness with custom judge, e.g because the judge use random output, lucky solver solve easy case only (hard case doesn't appear).. There's also other solution: use multiple cases in one file (small constraints, but so many cases), so it isn't easy to find the answers with binary search (useless if you find 1 or 2 answers only, no speedup) (because so many cases and large output), like TIP1 ;-)

Last edit: 2013-02-03 17:37:06
2013-02-03 14:52:52 Francky
Once AC anybody can find the 2 answers with binary search. Psetter should use in such cases a custom judge like in my TIP3 problem.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.