16909번 - 카드 구매하기 3

욱제는 민규네 동네에서 유행하는 PS카드를 구매하려고 한다. 욱제가 방문한 카드 가게에는 총 N개의 카드가 일렬로 놓여져 있고, i번째 카드의 능력치는 A_i이다.

욱제는 진열된 카드를 연속해서 구매하는 것을 좋아한다. 즉, 욱제는 i번째 카드부터 j번째 카드를 구매하게 된다. 구매한 카드의 가격은 능력치에 영향을 받는다. 카드를 구매하는 비용은 구매하려고 하는 카드 능력치의 최댓값에서 최솟값을 뺀 값이다.

예를 들어, 카드의 능력치가 [2, 5, 3]인 경우, 욱제는 이 카드를 6가지 방법으로 구매할 수 있다.

• i = 1, j = 1: [2], 가격: 2-2 = 0
• i = 1, j = 2: [2, 5], 가격: 5-2 = 3
• i = 1, j = 3: [2, 5, 3], 가격: 5-2 = 3
• i = 2, j = 2: [5], 가격: 5-5 = 0
• i = 2, j = 3: [5, 3], 가격: 5-3 = 2
• i = 3, j = 3: [3], 가격: 3-3 = 0

욱제가 카드를 구매할 수 있는 방법을 모두 구하고, 그 때 가격의 합을 구해보자.

첫째 줄에 진열대에 놓인 카드의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 카드의 능력치 A₁, A₂, ..., A_N(1 ≤ A_i ≤ 1,000,000)이 주어진다.

첫째 줄에 카드를 구매하는 모든 방법의 가격의 합을 출력한다.