COCI 2014/2015 contest2 6- Zeno의 전당포(NORMA) > 문제은행 : 정보올림피아드&알고리즘




2900 : Zeno의 전당포(NORMA)

제한시간
3000 ms   
메모리제한
64 MB   
해결횟수
2 회   
시도횟수
126 회   

문제

강욱이는 미스터 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가 된다.



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


입력형식

첫 행에 강욱이가 받은 정수배열의 원소의 개수 N( 1 ≤ N ≤ 500,000)이 입력된다.
다음 행부터 N개의 행에 걸쳐 1이상 1억 이하의 정수가 입력된다.

테스트 케이스의 40%는 N < 5000 이다.


출력형식

강욱이가 받은 정수배열의 모든 연속부분수열에서 나올 수 있는 가격의 합을 하나의 행에 출력한다.
출력 결과가 너무 클 수 있으므로 10억으로 나눈 나머지를 출력한다.


입력 예

2
1
3

출력 예

16

입력 예

4
2
4
1
4

출력 예

109

입력 예

6
8
1
3
9
7
4

출력 예

1042


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP