시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 51 18 16 48.485%

문제

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

욱제는 진열된 카드를 연속해서 구매하는 것을 좋아한다. 즉, 욱제는 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)이 주어진다.

둘째 줄에는 카드의 능력치 A1, A2, ..., AN(1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

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

예제 입력 1

3
2 5 3

예제 출력 1

8

출처