#2996. 流星

流星

题目描述

给出一个长度为 nn 的序列 A=a1,a2,...,anA={a_1,a_2,...,a_n},你可以对其进行任意次交换操作,每次交换任意两个数。在你操作之后,设序列 BBAA 的前缀和数组,请你让 BB 序列所有数的和最大,并输出这个总和。

序列 BB 的定义为 bi=j=1iaib_i=\sum_{j=1}^i a_i。换句话说,bib_i 的值为 AA 中以 ii 为结尾的前缀之和。

输入格式

第一行一个整数 nn,表示序列长度。

第二行 nn 个整数,表示序列 AA

输出格式

一行一个整数,表示 BB 序列最大的和。

5 
2 4 3 1 4
50
13
1 1 4 5 1 4 1 9 1 9 8 1 0
458

数据范围

对于所有数据,1n2×1051\le n\le 2\times10^50ai1050\le a_i\le 10^5

数据编号 nn aia_i
1 10\le 10 100\le 100
2 105\le 10^5
3
4 200\le 200 100\le 100
5 105\le 10^5
6 2×103\le 2\times 10^3 100\le 100
7 105\le 10^5
8 2×105\le 2\times 10^5 100\le 100
9 105\le 10^5
10