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

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

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

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

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

Хөгшин бор баавгай Лимак найзуудтайгаа боулин тоглох дуртай. Өнөөдөр тэрээр их өөдрөг байгаа ба өөрийнхөө дээд амжилтыг шинэчлэхээр зорьж гэнэ.

Бөмбөгийг өнхрүүлсэн тоглогч ямар нэгэн оноо авна. Оноо бүхэл тоо байна. (Сөрөг байж болно) $i$ дэх удаагаа бөмбөгийг өнхрүүлэхэд авсан оноог $i$-ээр үржүүлнэ. Мөн нийт оноо нь тэдгээр оноонуудын нийлбэр байна. Тэгвэл $k$ удаа бөмбөг өнхрүүлэн $s_{1}, s_{2}, ..., s_{k}$ гэсэн оноо авсан бол нийт оноо $\sum\limits_{i=1}^{k}{i \cdot s_i}$ байна. Бөмбөг өнхрүүлээгүй бол $0$ оноонд тооцно.

Лимак $n$ удаа бөмбөг өнхрүүлэн $i$ дэх өнхрүүлэлтэнд $a_{i}$ оноо авсан гэе. Тэрээр нийт оноогоо хамгийн их байлгахыг хүсч байгаа ба нэгэн санаа сэдэж гэнэ. Тэрээр ямар нэгэн зүйл түүнд саад болсон гэх шалтгаанаар зарим өнхрүүлэлтээ цуцлах юм.

Лимак хэдэн ч өнхрүүлэлтээ цуцлаж чадна. Бүх өнхрүүлэлтээ цуцлах, эсвэл алийг нь ч цуцлахгүй байж чадна. Нийт оноог Лимак өнхрүүлэлт цуцлаагүй мэт тооцно. Жишээний тайлбарыг харна уу. Лимакийн авч чадах хамгийн өндөр оноог ол?

Оролт

Эхний мөрөнд $n$ ($1 ≤ n ≤ 10^{5}$) гэсэн бүхэл тоо байна.

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

Гаралт

Түүний авч чадах хамгийн өндөр оноог хэвлэ.

Орчуулсан: Бат-Од

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

Оролт
5
-2 -8 0 5 -3
Гаралт
13
Оролт
6
-10 20 -30 40 -50 60
Гаралт
400

Тэмдэглэл

Эхний жишээнд Лимак $-8$ ба $-3$ оноо авсан өнхрүүлэлтүүдийг цуцална. Тэгээд түүнд $-2, 0, 5$ гэсэн оноонуудын дараалал үлдэнэ. Нийт оноо нь $1 \cdot (-2) + 2 \cdot 0 + 3 \cdot 5 = 13$ гэж тооцогдоно.

Хоёр дахь жишээнд Лимак $-50$ оноо авсан өнхрүүлэлтийг цуцална. Нийт оноо $1 \cdot (-10) + 2 \cdot 20 + 3 \cdot (-30) + 4 \cdot 40 + 5 \cdot 60 = 400$ гэж тооцогдоно.

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