E. Мишка и боулинг
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Лимак — старый бурый мишка. Он часто ходит в боулинг с друзьями. Сегодня он чувствует себя очень хорошо и старается побить собственный рекорд!

За бросок он получает целое число (возможно, отрицательное) очков. В конце игры счет за i-й бросок умножается на i и все счета суммируются. Таким образом, за k бросков на s1, s2, ..., sk очков общий счёт будет равен . В частности, если бросков не было, общий счёт полагается равным 0.

Лимак сделал n бросков и получил счет ai за i-й из них. Он хочет максимизировать свой общий счет и придумал интересную мысль. Он отменит некоторые броски, сказав, что его что-то отвлекло или что дул сильный ветер.

Лимак может отменить любое количество бросков (возможно, все или ни один из них). Общий счет подсчитывается так, как будто были только не отмененные броски (прочитайте пояснения к тестам). Какой максимальный общий счет может получить Лимак?

Входные данные

Первая строка содержит единственное целое число n (1 ≤ n ≤ 105).

Вторая строка содержит n целых чисел через пробел a1, a2, ..., an (|ai| ≤ 107) — очки, полученные Лимаком за броски в порядке их совершения.

Выходные данные

Выведите максимальный возможный общий счет после отмены некоторых бросков.

Примеры
Входные данные
5
-2 -8 0 5 -3
Выходные данные
13
Входные данные
6
-10 20 -30 40 -50 60
Выходные данные
400
Примечание

В первом примере Лимак должен отменить броски со счетами  - 8 и  - 3. Затем у него останутся три броска со счетами  - 2, 0, 5. Общий счет — 1·( - 2) + 2·0 + 3·5 = 13.

Во втором примере Лимак должен отменить бросок со счетом  - 50. Общий счет равен 1·( - 10) + 2·20 + 3·( - 30) + 4·40 + 5·60 = 400.