У маленькой девочки Алёны сегодня день рождения. У ее мамы есть массив из n цветков. У каждого цветка есть настроение, настроение i-го цветка равно a_i. Настроение может быть положительным, нулевым или отрицательным.

Назовем подмассивом произвольную последовательность из подряд идущих элементов массива. Мама предложила девочке некоторый набор подмассивов массива цветков. Алёне хочет выбрать некий набор подмассивов из набора, предложенного мамой. После того, как она это сделает, каждый цветок из массива прибавит к счастью девочки свое настроение, умноженное на количество выбранные девочкой подмассивов, в которые этот цветок попал.

Например, пусть у мамы есть 5 цветков, а их настроения равны 1,  - 2, 1, 3,  - 4. Пусть мама выбрала подмассивы (1,  - 2), (3,  - 4), (1, 3), (1,  - 2, 1, 3). Тогда если девочка выберет третий и четвертый подмассивы, то:

• первый цветок добавит к счастью Алёны 1·1 = 1, потому что он попал в один подмассив,
• второй цветок добавит ( - 2)·1 =  - 2, потому что он попал в один подмассив,
• третий цветок добавит 1·2 = 2, потому что он попал в два подмассива,
• четвертый цветок добавит 3·2 = 6, потому что он попал в два подмассива,
• пятый цветок добавит ( - 4)·0 = 0, потому что он не попал ни в один подмассив.

Таким образом, к счастью Алёны добавится 1 + ( - 2) + 2 + 6 + 0 = 7. Алена хочет выбрать такие подмассивы из предложенных мамой, чтобы прибавка к ее счастью была максимально возможной. Помогите ей сделать это!

Алена может выбрать любое количество подмассивов, даже 0 или все, что были предложены мамой.