DIFERENC - DIFERENCIJA

no tags 

 

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
input
4
7
5
7
5
input
4
3
1
7
2
output
4
output
12
output
31

 

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)(曾毅昆): 2013-02-03 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: 2013-02-03 17:37:06
Francky: 2013-02-03 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:2012-02-13
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