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 là [1,2,3] thì giá trị của dãy là 9 (GTNN = 1, GTLN = 3, 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 đó.

Input

• Dòng đầu là số nguyên dương N, là số phần tử của mảng A (1\(\leq\)N\(\leq\)\(10^6\))
• Dòng thứ hai là các số nguyên \(A_{1}\),\(A_{2}\),...,\(A_{N}\) (các giá trị \(A_{i}\) không vượt qua \(10^9\))

Output

• Một dòng duy nhất sau khi modulo 1e9.

Scoring

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

Example

2
1
3 

16