E. Бүтээгдэхүүний нийлбэр

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

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

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

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

Блейк бол Крисийн босс гэсэн хэдий ч энэ нь тэдний нөхөрлөлийг сүйтгэдэггүй. Тэд ихэвчлэн зарим утгыг хамгийн их байлгах сэтгэл хөдөлгөм асуудлуудын талаар ярихын тулд цэнгээний газар уулздаг. Энэ удаагийн асуудал бол маш онцгой.

Танд $n$ урттай $a$ массив өгөгдсөн. Массивын тодорхойломж нь   гэх утга ба бүтээгдэхүүнүүдийн утгууд буюу $a_{i}$ ба $i$-н үржвэрүүдын нийлбэр. Дараах үйлдлийг ганц л удаа хийж болно: массивийн зарим элементийг авч дурын байрлалдаа тавих. Элемэнтийг массивын эхлэл болон төгсгөлрүү зөөж болно. Мөн буцаагаад эхний байршилд нь тавихыг зөвшөөрнө. Ингээд зорилго бол хамгийн их тодорхойломжийн утгатай массивыг олох.

Оролт

Оролтын эхний мөрөнд ганц бүхэл тоон утга $n$ ($2 ≤ n ≤ 200 000$) байх ба $a$ массивын хэмжээ.

Хоёр дахь мөрөнд $n$ ширхэг бүхэл тоон утга $a_{i}$ ($1 ≤ i ≤ n$, $|a_{i}| ≤ 1 000 000$) байх ба $a$ массивын элементүүд юм.

Гаралт

Хариу болох бүхэл тоон утга буюу нэгээс илүүгүй үйлдэл хийгээд олж авах боломжтой $a$ массивын тодорхойломжийн утгыг олж хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

Оролт
4
4 3 2 5
Гаралт
39
Оролт
5
1 1 2 7 1
Гаралт
49
Оролт
3
1 1 2
Гаралт
9

Тэмдэглэл

Эхний жишээн дээр эхний элементийг авч гурав дахь элементийн($5$-ийн өмнө) урд тавина. Иймээс хариу $3*1 + 2*2 + 4*3 + 5*4 = 39$ болно.

Хоёр дахь жишээн дээр тав дахь элементийг авч гурав дахь элементийн урд тавина. Иймээс хариу $1*1 + 1*2 + 1*3 + 2*4 + 7*5 = 49$ болно.

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