노르마의 배열 가격 합

미르코는 생일에 할머니 노르마에게서 정수 배열을 하나 받았다. 다른 아이처럼 돈을 기대했지만 손에 들어온 것은 배열이었다. 다행히 미르코가 사는 동네에는 배열을 사들이는 전당포가 있다.

정수 배열의 가격은 $\min \times \max \times L$ 쿠나이다. $\min$은 배열에서 가장 작은 정수, $\max$는 가장 큰 정수, $L$은 배열의 길이이다.

미르코는 자기 배열에서 연속한 원소로 이루어진 부분 배열 하나를 팔려고 한다. 어느 것을 팔지 고민하다가 팔 수 있는 모든 연속 부분 배열의 가격을 전부 더해 보았다. 계산이 맞는지 확인하고 싶어서 같은 값을 구해 달라고 한다.

가격 합의 마지막 아홉 자리만 알면 되므로 큰 수나 실수를 다룰 필요는 없다.

첫째 줄에 정수 $N$이 주어진다. ($1 \le N \le 500\,000$)

다음 $N$개 줄에 미르코 배열의 원소가 순서대로 한 줄에 하나씩 주어진다. 각 원소는 $1$ 이상 $10^8$ 이하의 정수이다.

연속한 원소로 이루어진 모든 부분 배열의 가격을 더한 값의 마지막 아홉 자리를 첫째 줄에 정수 하나로 출력한다. 즉, 가격의 합을 $10^9$으로 나눈 나머지를 출력한다. 앞자리 0은 출력하지 않는다.

첫 번째 예제에서 배열은 정수 $1$과 $3$으로 이루어진다. 팔 수 있는 연속 부분 배열은 $(1)$, $(3)$, $(1, 3)$이고 가격은 차례로 $1$, $9$, $6$이므로 합은 $16$이다.

두 번째 예제에서 팔 수 있는 연속 부분 배열은 $(2)$, $(4)$, $(1)$, $(4)$, $(2, 4)$, $(4, 1)$, $(1, 4)$, $(2, 4, 1)$, $(4, 1, 4)$, $(2, 4, 1, 4)$이고 가격은 차례로 $4$, $16$, $1$, $16$, $16$, $8$, $8$, $12$, $12$, $16$이므로 합은 $109$이다.