题目描述

给定一个长度为 $n$ 的序列 $a_{1\dots n}$。

你要求一个 $a$ 的子序列 $b_{1\dots m}$（可以为空），使得 $\sum_{i=1}^m ib_i$ 的值最大。

$n \le 10^5$，$|a_i| \le 10^7$。

输入格式

第一行一个整数 $n$，$1\le n\le 10^{5}$。

第二行 $n$ 个整数 $a_i$，$|a_{i}|\le 10^{7}$。

输出格式

一个整数表示答案。

5
-2 -8 0 5 -3

13

6
-10 20 -30 40 -50 60

400