강욱이는 미스터 eaststar로부터 생일선물로 정수배열을 받았다. 다른 학생들처럼 현금을 받는 것이 더 좋았을 텐데... 정수배열이 생일선물이라니... ㅠㅠㅠ

 하지만 운 좋게도 Zeno가 운영하는 전당포가 강욱이의 집에서 가까이 있었고 Zeno의 전당포에서는 정수배열을 구입하고 있었다. Zeno가 정수배열을 구입하는 방식은 나름 규칙을 갖고 있었는데 주어진 배열에서 1개 이상의 연속된 부분을 선택한 후 그 중 최대값과 최소값, 그리고 선택한 부분의 원소의 개수를 곱한 값을 구입가격으로 계산하였다.

예를 들어 { 2, 4, 1, 4 } 라는 정수 배열이 주어지고 이중에서 선택한 부분이 { 2, 4, 1}라고 하자. 그러면 Zeno가 구입하는 구입가격은 최대값은 4, 최소값은 1, 원소의 개수는 3이므로 4 * 1 * 3 = 12가 된다.

재미있다고 생각한 강욱이는 자신이 받은 정수배열의 모든 연속부분수열에서 나올 수 있는 가격의 합이 궁금해졌다. 예를 들어 위 예제의 경우 나올 수 있는 연속부분수열은 {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가 된다.

강욱이의 궁금증을 해결할 수 있는 프로그램을 작성해보자.

첫 행에 강욱이가 받은 정수배열의 원소의 개수 N( 1 ≤ N ≤ 500,000)이 입력된다.
다음 행부터 N개의 행에 걸쳐 1이상 1억 이하의 정수가 입력된다.

테스트 케이스의 40%는 N < 5000 이다.

강욱이가 받은 정수배열의 모든 연속부분수열에서 나올 수 있는 가격의 합을 하나의 행에 출력한다.
출력 결과가 너무 클 수 있으므로 10억으로 나눈 나머지를 출력한다.