C. NORMA

Bộ nhớ: 256 MiB Thời gian: 500 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản

Đề bài

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.

Dữ liệu vào:

  • Dòng đầu là số nguyên N\ (1≤N≤5×10^5) ;
  • N Dòng sau, mỗi dòng một số thể hiện dãy số của Mirko (có giá trị trong đoạn [1, 10^8]) .

Dữ liệu ra:

  • Ghi ra kết quả theo modulo 10^9 .

Ví dụ:

Dữ liệu vào:
2
1
3
Dữ liệu ra:
16
Dữ liệu vào:
4
2
4
1
4

Dữ liệu ra:

109

Giới hạn:

  • 40\% N≤5000 .