Теофанис легко зацикливается на задачах перед сном, и они часто снятся ему в кошмарах. Чтобы справиться с этим, он обратился к своему врачу, доктору Эмиксу.
В последнем кошмаре у него был массив \(a\) длины \(n\), и он хотел разбить его на непустые подмассивы\(^{\dagger}\) так, чтобы каждый элемент находился ровно в одном из подмассивов.
Например, массив \([1,-3,7,-6,2,5]\) можно разбить на \([1] [-3,7] [-6,2] [5]\).
Киприотское значение такого разбиения равняется \(\Sigma_{i=1}^{k} i \cdot \mathrm{sum}_i\), где \(k\) — количество подмассивов, на которое мы разделили массив, а \(\mathrm{sum}_i\) — сумма \(i\)-го подмассива.
Киприотское значение разбиения массива \([1] [-3,7] [-6,2] [5] = 1 \cdot 1 + 2 \cdot (-3 + 7) + 3 \cdot (-6 + 2) + 4 \cdot 5 = 17\).
Теофанису интересно, каково максимальное киприотское значение среди всех разбиений массива.
\(^{\dagger}\) Массив \(b\) является подмассивом массива \(a\), если \(b\) может быть получен из \(a\) удалением нескольких (возможно, нуля или всех) элементов из начала и нескольких (возможно, нуля или всех) элементов из конца. В частности, массив является подмассивом самого себя.
Примечание
В первом наборе входных данных для получения максимального киприотского значения мы разобьём массив на \([1][-3][7][-6][2][5]\), что даст нам: \(\Sigma_{i=1}^{k} i \cdot \mathrm{sum}_i = 1 \cdot 1 + 2 \cdot (-3) + 3 \cdot 7 + 4 \cdot (-6) + 5 \cdot 2 + 6 \cdot 5 = 32\).
Аналогично, во втором наборе входных данных мы разбиваем массив на \([2][9,-5,-3]\), что дает нам \(\Sigma_{i=1}^{k} i \cdot \mathrm{sum}_i = 1 \cdot 2 + 2 \cdot (9 + (-5) + (-3)) = 4\).