강욱이는 미스터 eaststar로부터 생일선물로 정수배열을 받았다. 다른 학생들처럼 현금을 받는 것이 더 좋았을 텐데... 정수배열이 생일선물이라니... ㅠㅠㅠ

하지만 운 좋게도 Zeno가 운영하는 전당포가 강욱이의 집에서 가까이 있었고 Zeno의 전당포에서는 정수배열을 구입하고 있었다. Zeno가 정수배열을 구입하는 방식은 나름 규칙을 갖고 있었는데 주어진 배열에서 1개 이상의 연속된 부분을 선택한 후 그 중 최대값과 최소값, 그리고 선택한 부분의 원소의 개수를 곱한 값을 구입가격으로 계산하였다. 예를 들어 { 2, 4, 1, 4 } 라는 정수 배열이 주어지고 이중에서 선택한 부분이 { 2, 4, 1}라고 하자. 그러면 Zeno가 구입하는 구입가격은 최대값은 4, 최소값은 1, 원소의 개수는 3이므로 4 * 1 * 3 = 12가 된다.

재미있다고 생각한 강욱이는 자신이 받은 정수배열의 모든 연속부분수열에서 나올 수 있는 가격의 합이 궁금해졌다. 예를 들어 위 예제의 경우 나올 수 있는 연속부분수열은 {2}, {4}, {1}, {4}, {2,4}, {4, 1}, {1, 4}, {2, 4, 1}, {4, 1, 4}, {2, 4, 1, 4}이고 각각의 경우 가격은 4, 16, 1, 16, 16, 8, 8, 12, 12, 16이 되므로 그 합은 109가 된다.

강욱이의 궁금증을 해결할 수 있는 프로그램을 작성해보자.

#2900 upload 19 done 1 how_to_reg 1

Zeno의 전당포(NORMA) timer 3s memory 64MB

#2900

Zeno의 전당포(NORMA) 3s 64MB