점프

시간 제한2초메모리 제한1024 MB

요약

건물 높이가 주어질 때, 사이의 건물이 모두 두 끝보다 낮은 건물 쌍끼리 점프하는 최소 비용(높이 차의 제곱 합)을 모든 쌍에 걸쳐 구하고 10억 7의 나머지를 출력합니다.

문제

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

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

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

$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$ 로 나눈 나머지를 출력한다.