Page not loading? Try clicking here.
Placeholder

#8483
Subtask

배열의 가치 3s 64MB

Problems

N개의 자연수로 구성된 배열 [~A_1, A_2, ..., A_N~] 이 있다.

"배열의 가치"는, 아래와 같이 정의한다.

배열의 가치 = 배열의 길이 × 그 배열의 최댓값 × 그 배열의 최솟값

예를 들어, 배열 [ 5 2 6 1 ] 의 가치는 4 × 6 × 1 = 24 이다.

[~A_1, A_2, ..., A_N~] 의 모든 "연속 부분 배열" 에 대하여, 그들의 가치의 총합을 구해보자.


Input

첫 줄에 N 이 입력된다. ( 1 ≤ N ≤ 500,000 )

두 번째 줄에 N 개의 자연수들이 입력된다. ( 1억 이하 )


Output

모든 연속 부분 배열들의 가치 총합을, 10억 7 로 나눈 나머지를 출력하여라.


Subtask

# Score Condition
#110

1 ≤ N ≤ 100

#215

1 ≤ N ≤ 5000

#315

A_i ≤ 2

#415

A_i ≤ A_{i+1}

#545

제약 조건 없음


Example #1

4
5 2 6 1
200

Example #2

5
2 1 3 2 4
162

Example #3

20
3 6 38 31 34 386 2 138 38 39 98 76 1 888 35 1234 66 98 71 9993
121892091

Source

COCI 2014/2015 Contest #2 6번

You must sign in to write code.