지워진 최댓값

시간 제한1초메모리 제한512 MB

요약
인덱스 순서를 지키는 두 개의 서로 겹치지 않는 구간을 지웠을 때 남는 원소의 최댓값을 모든 경우에 대해 더한다.
난이도

보통10점 중 6점

유형
조합론, 누적 합, 수학, 구현
정답자
아직 제출이 없습니다

문제

길이가 NN인 순열 AA가 주어진다. 1≤i≤j<k≤l≤N1 \le i \le j < k \le l \le N인 모든 가능한 (i,j,k,l)(i, j, k, l)에 대해, AA에서 \[i,j]\[i, j] 구간과 \[k,l]\[k, l] 구간을 삭제했을 때의 최댓값의 합을 구하여라. 비어있는 배열의 최댓값은 00으로 가정한다.

입력

첫 번째 줄에 NN이 주어진다. (3≤N≤105)(3 \le N \le 10^5)

두 번째 줄에 순열 AA를 이루는 정수 NN개가 공백으로 구분되어 주어진다. (1≤A_i≤N;(1 \le A\_i \le N; 모든 A_iA\_i는 서로 다르다.))

출력

답을 109+710^9+7로 나눈 나머지를 출력한다.

힌트

AA의 \[s,e]\[s, e] 구간은 A_s,A_s+1,⋯ ,A_eA\_s, A\_{s+1}, \cdots, A\_e를 의미한다.

예제1

  1. 예제 1

    입력
    4
4 2 3 1
    예상 출력
    35