Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NORMA - Lại là dãy số

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, 108])

Output

Ghi ra kết quả theo modulo 109

Example

Input:

2

1

3 Output: 16

Được gửi lên bởi:Alex & Friends
Ngày:2014-12-07
Thời gian chạy:3s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:COCI

hide comments
2017-10-14 10:17:54
tham khảo tại đây: http://bfy.tw/ETE1
2017-10-14 09:30:33
http://bfy.tw/ETCt
2017-10-10 04:06:11
Liek
2017-10-03 06:25:10
Bai nay divide and conquer code 100 lines ez gg,
lien he https://www.facebook.com/vong.phanxuan de tham khao code
2015-10-22 03:22:30 Anh Vu
COCI 2014-2015
2015-10-02 10:42:38 Nguyễn Hữu Phong
1*1*1+3*3*1+1*3*2=16
2015-07-29 05:54:28 ■■‡[ND] Bee Sociu■■‡
1.1.1+1.3.2+3.3.1 = 16

Last edit: 2015-07-29 05:55:07
2015-05-28 18:33:37 Phong
test tại s ra 16 vậy ??
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.