A60050.取与得

Alice 最近在整理她的数据序列。她手中有一个长度为 $n$ 的数组，但她觉得这个数组的当前排列方式不够理想。于是，她决定通过删除一些元素来构造一个新的非空子序列,并将子序列按照一定方法重新排列，生成一个新的数组 $a_1, a_2, \dots, a_k$（其中 $1 \leq k \leq n$）。

为了量化新序列的满意度，Alice 设计了一个评价标准：对于长度为 $k$ 的子序列，其满意度定义为

$$\sum_{i=1}^k (k - i + 1) \times a_i$$

请你帮助 Alice 找出所有可能的非空子序列中，能够使满意度最大的那个子序列，并输出其满意度值。

第一行输入一个整数 $n$ ，代表原数组的长度 。

接下来一行输入 $n$ 个整数$arr_i$ ，代表原数组的每一个元素。

输出一个整数，表示可能的最大满意度。

数据范围

• $1 \le n \le 10^5$ 。
• $-10^6 \le arr_i \le 10^6$ 。