페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8483
서브태스크

배열의 가치 3s 64MB

문제

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

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

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

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

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


입력

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

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


출력

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


부분문제

번호 점수 조건
#110점

1 ≤ N ≤ 100

#215점

1 ≤ N ≤ 5000

#315점

A_i ≤ 2

#415점

A_i ≤ A_{i+1}

#545점

제약 조건 없음


예제 #1

4
5 2 6 1
200

예제 #2

5
2 1 3 2 4
162

예제 #3

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

출처

COCI 2014/2015 Contest #2 6번
로그인해야 코드를 작성할 수 있어요.