LƯU Ý: LÀM CẨN THẬN VÌ BÀI NÀY RẤT DỄ RUNTIME ERROR

Cho dãy \(A\) có \(N\) phần tử. Giá trị của một dãy con liên tiếp trong \(A\) là tích ba chỉ số: Giá trị nhỏ nhất của dãy con, Giá trị lớn nhất của dãy con và Độ dài dãy con.

Ví dụ: mảng \(A = [1, 2, 3, 4]\) có dãy con liên tiếp là \([1, 2, 3]\) thì giá trị của dãy con này là \(1 \cdot 3 \cdot 3 = 9\) (với \(\min = 1, \max = 3, \text{size} = 3\)).

Nhiệm vụ của bạn là tính tổng tất cả các giá trị của các dãy con liên tiếp đó.

Input

• Dòng đầu là số nguyên dương \(N\), là số phần tử của mảng \(A\) (\(1 \le N \le 10^6\)).
• Dòng thứ hai là các số nguyên \(A_1, A_2, \dots, A_N\) (\(|A_i| \le 10^9\)).

Output

• Một dòng duy nhất là tổng tìm được sau khi modulo \(10^9\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N \le 5000\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

2
1 3

16