시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB85322442.105%

문제

길이가 $N$인 수열 $A_1, A_2, \dots, A_N$이 있을 때, 이 수열의 점수는 다음과 같이 정의한다.

$$ \min_{i=1}^{N} A_i \cdot \max_{i=1}^{N} A_i $$

음이 아닌 정수로 이루어진 수열 $B$가 주어질 때, $B$의 모든 연속 부분 수열에 대한 점수의 합을 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수열 $B$의 길이 $N$이 주어진다. $(1 \le N \le 200\,000)$

두 번째 줄에 정수 $B_1, B_2, \dots, B_N$이 공백으로 구분되어 주어진다. $(0 \le B_i \le 10^9)$

출력

$B$의 모든 연속 부분 수열에 대한 점수의 합을 출력한다. 단, 정답이 매우 커질 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

예제 입력 1

5
1 5 3 4 2

예제 출력 1

143

길이가 $1$인 부분 수열은 $[1], [5], [3], [4], [2]$이고 각 점수는 $1, 25, 9, 16, 4$이다.

길이가 $2$인 부분 수열은 $[1,5], [5,3], [3,4], [4,2]$이고 각 점수는 $5, 15, 12, 8$이다.

길이가 $3$인 부분 수열은 $[1,5,3], [5,3,4], [3,4,2]$이고 각 점수는 $5, 15, 8$이다.

길이가 $4$인 부분 수열은 $[1,5,3,4], [5,3,4,2]$이고 각 점수는 $5, 10$이다.

길이가 $5$인 부분 수열은 $[1,5,3,4,2]$이고 점수는 $5$이다.

따라서 모든 점수의 합은 $143$이다.

출처

Camp > ICPC Sinchon Algorithm Camp > 2022 ICPC Sinchon Summer Algorithm Camp Contest > 중급 D번