Giải bài trực tuyến

Mirko có một dãy số, và cô không thích nó nữa, cô quyết định bán nó đi vào ngày mai. Khi một dãy số nào đó được bán ra ngoài, cô sẽ nhận được giá tiền là min.max.len với min là số nhỏ nhất trong dãy, max là số lớn nhất trong dãy, và len là độ dài của dãy số đó. Cô quyết định bán một đoạn con liên tiếp trong dãy số của cô. Cố muốn biết rằng, tổng giá trị của tất cả các dãy con liên tiếp trong dãy số của cô là bao nhiêu. 

Input

• Dòng đầu là số nguyên N (N ≤ 500.000)
• Dòng sau gồm N số thể hiện dãy số của Mirko (có giá trị trong đoạn [1, 10⁸])

Output

Ghi ra kết quả theo modulo 10⁹

Example

Input:
2
1
3

Output:
16