DAO ĐỘNG CÓ TRỌNG SỐ

Cho dãy số nguyên a[1], a[2], ..., a[n]. Các phần tử của dãy có thể âm, dương hoặc bằng 0.

Với mỗi đoạn con liên tiếp, không rỗng [l, r] (1 <= l <= r <= n), đặt:

• S(l, r) là tổng các phần tử từ a[l] đến a[r].
• M(l, r) là giá trị lớn nhất trong đoạn [l, r].
• m(l, r) là giá trị nhỏ nhất trong đoạn [l, r].

Sức nặng dao động của đoạn [l, r] được định nghĩa bằng:

W(l, r) = (M(l, r) - m(l, r)) * S(l, r)

Hãy tính tổng sức nặng dao động của tất cả các đoạn con liên tiếp không rỗng:

F = SUM(W(l, r)), với mọi 1 <= l <= r <= n.

Vì F có thể rất lớn hoặc âm, hãy in phần dư không âm của F khi chia cho 1000000007.

Dữ liệu vào

• Dòng đầu chứa số nguyên n.
• Dòng thứ hai chứa n số nguyên a[1], a[2], ..., a[n].

Dữ liệu ra

In một số nguyên duy nhất: phần dư không âm của F theo modulo 1000000007, nằm trong khoảng từ 0 đến 1000000006.

Giới hạn

• 1 <= n <= 200000.
• -1000000000 <= a[i] <= 1000000000.

Ví dụ 1

Input

3
1 3 2

Output

25

Giải thích: Các đoạn chỉ chứa một phần tử đều có M(l,r) = m(l,r) nên sức nặng bằng 0.

Vậy F = 8 + 5 + 12 = 25.

Ví dụ 2

Input

3
-2 3 -1

Output

13

Giải thích: Ba đoạn có ít nhất hai phần tử đóng góp lần lượt 5, 8 và 0, nên F = 13.

Ví dụ 3

Input

3
-3 0 2

Output

999999997

Giải thích: Tổng thực tế là F = -10; phần dư không âm khi chia cho 1000000007 là 999999997.

Phân nhóm điểm (100 điểm)

Lưu ý: Tổng S(l,r) có thể âm, nên W(l,r) cũng có thể âm. Phải in kết quả đã chuẩn hóa thành phần dư không âm.