시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 85 | 32 | 24 | 42.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$로 나눈 나머지를 출력한다.
5 1 5 3 4 2
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$이다.