문제
가게에 물건들이 있다.
물건들의 가격의 집합에 대하여, 해당 집합의 비용은 (집합의 최대 원소)*(집합의 최소 원소)*(집합의 크기)이다.
당신에게는 N개의 물건의 가격 정보가 주어진다.
당신이 해야할 것은, N개의 물건에 대하여 모든 연속한 부분집합의 비용의 합을 구하는 것이다.
물론, 답이 매우 커질 수 있으니, 비용의 마지막 9자리만 구해도 좋다.
입력
첫 번째 줄에 N이 주어진다.
두 번째 줄 부터 N 줄에 걸쳐, i번째 물건의 가격이 주어진다.
1 <= N <= 500 000
1 <= (각 물건의 가격) <= 100 000 000
출력
N개의 물건에 대하여 모든 연속한 부분집합의 비용의 합의 마지막 9자리를 출력하여라.
예제 #1
2
1
3
16
예제 #2
4
2
4
1
4
109
예제 #3
6
8
1
3
9
7
4
1042
로그인해야 코드를 작성할 수 있어요.