COCI '10 Contest 3 #5 Diferencija

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

Mirko discovered what Slavko did in the previous task, and decided to deal with something completely different from 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 Specification

The first line of input contains a single integer N (2 \leq N \leq 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 Specification

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

Sample Input 1

3
1
2
3

Sample Output 1

4

Sample Input 2

4
7
5
7
5

Sample Output 2

12

Sample Input 3

4
3
1
7
2

Sample Output 3

31

Comments

There are no comments at the moment.