## COCI '10 Contest 3 #5 Diferencija

View as PDF

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 is , and value of is .

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 , number of elements of the sequence. Next lines contain elements of the sequence. Each element is a positive integer not greater than .

#### 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