题目描述

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

序列 $B$ 的定义为 $b_i=\sum_{j=1}^i a_i$。换句话说，$b_i$ 的值为 $A$ 中以 $i$ 为结尾的前缀之和。

输入格式

第一行一个整数 $n$，表示序列长度。

第二行 $n$ 个整数，表示序列 $A$。

输出格式

一行一个整数，表示 $B$ 序列最大的和。

5 
2 4 3 1 4

50

13
1 1 4 5 1 4 1 9 1 9 8 1 0

458

数据范围

对于所有数据，$1\le n\le 2\times10^5$，$0\le a_i\le 10^5$。