문제
N개의 정수로 이뤄진 수열 A가 있다. D(i,j) 는 A의 i번째 원소 부터 j번째 원소를 포함하는 구간에서 최대값과 최소값의 차이를 뜻한다.
A = { 1,3,5,7,9 } 일 때 D( 2, 4 ) = |7-3| = 4가 된다.
수열 A가 주어졌을 때 가능한 모든 D(i,j)의 합을 구하는 프로그램을 작성하라.
입력
입력의 첫 줄에는 N(1≤N≤300,000) 이 주어진다. 그 다음 줄에는 수열 A의 첫번째, 셋째 줄에는 A의 두번째, …, 마지막 줄에는 N번째 원소가 입력된다. 입력되는 숫자는 100,000,000 이하의 양의 정수이다.
출력
수열 A가 주어졌을 때 가능한 모든 D(i, j)의 합을 출력한다.
예제 #1
3
1
2
3
4
예제 #2
4
7
5
7
5
12
예제 #3
3
1
7
2
17
출처
COCI 2010/2011 contest3 5
로그인해야 코드를 작성할 수 있어요.