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 TEST DATA
input
3
1
2
3
output
4
input
4
7
5
7
5
output
12
input
4
3
1
7
2
output
31
hide comments
(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20130203 16:23:39
@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: 20130203 17:37:06 

Francky:
20130203 14:52:52
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. 
Added by:  islam 
Date:  20120213 
Time limit:  0.254s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  COCI 2010/2011 Contest 3 by Adrian Satja Kurdija 