불균형 배열

n개의 원소로 이루어진 배열 a가 주어진다. 이 배열의 어떤 부분 구간의 불균형 값은 해당 구간의 최댓값과 최솟값의 차이이다. 배열의 불균형 값은 이 배열의 모든 부분 구간의 불균형 값의 합이다.

예를 들어, 배열 $[1, 4, 1]$의 불균형 값은 9이다. 이 배열에는 서로 다른 부분 구간이 6개 있기 때문이다:

• $[1]$ (인덱스 1부터 인덱스 1까지), 불균형 값은 0이다.
• $[1, 4]$ (인덱스 1부터 인덱스 2까지), 불균형 값은 3이다.
• $[1, 4, 1]$ (인덱스 1부터 인덱스 3까지), 불균형 값은 3이다.
• $[4]$ (인덱스 2부터 인덱스 2까지), 불균형 값은 0이다.
• $[4, 1]$ (인덱스 2부터 인덱스 3까지), 불균형 값은 3이다.
• $[1]$ (인덱스 3부터 인덱스 3까지), 불균형 값은 0이다.

배열 a의 불균형 값을 구해야 한다.

첫째 줄에는 배열 a의 크기를 나타내는 정수 n (1 ≤ n ≤ 106)가 하나 주어진다.

둘째 줄에는 배열의 원소인 n개의 정수 a1, a2... an (1 ≤ ai ≤ 106)이 주어진다.

a의 불균형 값인 정수 하나를 출력한다.