ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
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번

ログインしないとコードを書けません。