프로그램 명: coci_dif
제한시간: 1 초
[문제요약] N 개의 수열이 주어진다. N 개의 부분 수열로 만들어지는 차(최대-최소)의 합의 구하는것 이 문제이다.
예를 들어 N 이 3 이고 1 , 2 , 3 이 주어질 때 만들 수 있는 부분 수열은
- 1 , 2 ...차 2 - 1 = 1
- 2 , 3 ... 차 3 - 2 = 1
- 1 , 2 , 3 .. 차 3 - 1 = 2
합은 4
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.
입력
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.
출력
The first and only line of output must contain the requested sum.
입출력 예
입력
3
1
2
3
출력
4
입력
4
7
5
7
5
출력
12
입력
4
3
1
7
2
출력
31
출처:coci 2010
[질/답]
[제출 현황]
[푼 후(2)]