32383번 - 점프

문제

좌우로 길게 뻗은 도로를 따라 $N$채의 건물이 세워져 있다. 건물은 세워진 순서를 따라 왼쪽에서부터 1ドル$부터 $N$까지의 번호가 붙어 있고, $i$번 건물의 높이는 $H_i$이다.

뛰어난 신체 능력을 갖춘 채완이는 아래 조건을 만족하는 서로 다른 두 건물의 옥상 사이를 점프해서 이동할 수 있다.

• $a$번 건물과 $b$번 건물 사이에 있는 모든 건물의 높이가 $\min(H_a, H_b)$보다 작다.

이때, 한 번 점프하면 두 건물 높이 차이의 제곱만큼 체력을 소모한다. 두 건물이 좌우로 얼마나 떨어져 있는지는 체력 소모량에 영향을 미치지 않는다.

$D(a, b)$를 채완이가 $a$번 건물의 옥상에서 $b$번 건물의 옥상으로 점프만으로 이동하는 데 필요한 체력 소모량의 최솟값이라 했을 때, $\sum_{i=1}^{N-1} \sum_{j=i+1}^{N}{D(i, j)}$를 구해보자.

입력

첫째 줄에 건물의 개수 $N$이 주어진다. $(2 \le N \le 500\ 000)$

둘째 줄에 건물의 높이 $H_1, H_2, \cdots, H_N$이 공백으로 구분되어 주어진다. 모든 건물의 높이는 정수이며, 서로 다르다. $(1 \le H_i \le 10^9)$

출력

$\sum_{i=1}^{N-1} \sum_{j=i+1}^{N}{D(i, j)}$를 1ドル\ 000\ 000\ 007$로 나눈 나머지를 출력한다.

제한

힌트