F. Баавгай ба боулинг 4

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Лимак бол хөгшин бор баавгай. Тэрээр байн байн найзуудтайгаа явж боулинг тоглодог. Өнөөдөр тэрээр үнэхээр сайн байгаа бөгөөд өөрийнхөө дээд амжилтыг эвдэхээр оролдох юм!

Бөмбөг өнхрүүлж буй нэгэн оноо авна -- энэ нь бүхэл тоон (магадгүй сөрөг) оноо байна. $i$-дахь өнхрөлтийн оноо нь $i$-аар үржигдэх ба оноонууд нь нэмэгдээд явна. Иймд, $k$ ширхэг өнхрөлтийн оноонууд $s_{1}, s_{2}, ..., s_{k}$-уудын хувьд, нийт оноо нь байх юм. Хэрэв ямар ч өнхрөлт байхгүй бол нийт оноо нь $0$ байна.

Лимак $n$ өнхрөлт хийсэн ба тэдгээрийн $i$-дахь дээр $a_{i}$ оноо авсан. Тэрээр өөрийн оноогоо хамгийн их байлгахыг хүссэн бөгөөд түүнд сонирхолтой санаа төржээ. Тэрээр эхний хэсэг өнхрөлтүүд нь зөвхөн бие халаалт байсан ба тэрээр сүүлийн өнхрөлтүүд дээрээ сайн төвлөрөөгүй гэж хэлж болно. Илүү албан ёсоор хэлбэл, тэрээр $a_{1}, a_{2}, ..., a_{n}$-ын ямар ч угтвар болон ямар ч дагаврыг хасаж болно. Мөн бүх өнхрөлтүүдийг хасах болон алийг нь ч хасахгүй байх нь зөвшөөрөгдсөн.

Хэрэв зөвхөн үл хасагдах өнхрөлтүүд үлдвэл нийт оноо нь бодогдох юм. Ингэснээр эхний үл хасагдах өнхрөлт нь $1$-ээр үржигдэнэ, 2-дахь үл хасагдах өнхрөлт нь $2$-оор үржигдэнэ гэх мэт сүүлийн үл хасагдах өнхрөлт хүртэл үргэлжлэх юм.

Тэгвэл Лимак хамгийн ихдээ нийт хэдэн оноо авах вэ?

Оролт

Эхний мөрөнд ганц бүхэл тоо $n$ ($1 ≤ n ≤ 2*10^{5}$) өгөгдөнө -- энэ нь Лимак-ын хийх нийт өнхрөлтийн тоог илэрхийлнэ.

2-дахь мөрөнд $n$ ширхэг бүхэл тоонууд $a_{1}, a_{2}, ..., a_{n}$ ($|a_{i}| ≤ 10^{7})$-ууд өгөгдөнө -- эдгээр нь Лимак-ын өнхрөлтүүдийн оноог илэрхийлнэ.

Гаралт

Өнхрөлтүүд хассаны дараах боломжит хамгийн их нийт оноог хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
6
5 -1000 1 -3 7 -8
Гаралт
16
Оролт
5
1000 1000 1001 1000 1000
Гаралт
15003
Оролт
3
-60 -70 -80
Гаралт
0

Тэмдэглэл

Эхний жишээнд, Лимак эхний 2 өнхрөлтийг болон сүүлийн өнхрөлтийг хасах ёстой. Тэрээр $1,-3,7$ өнхрөлтүүдтэй үлдэх ба эдгээр нь түүнд нийтдээ $1*1 + 2*( - 3) + 3*7 = 1 - 6 + 21 = 16$ оноо өгнө.

Сэтгэгдлүүдийг ачааллаж байна...