题目描述

有 $n$ 个整数 $a_1,a_2,\ldots,a_n$。$f_0=0,f_i= \left\{ \begin{aligned} & f_{i-1} & \ f_{i-1}\times a_i>0, \\ & f_{i-1}+a_i & \ f_{i-1}\times a_i\le 0.\\ \end{aligned} \right. $

重排 $a$ 使得得到的 $f_n$ 最大。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1,\dots,a_n$。

输出格式

一行一个整数，表示答案。

5
7 5 -4 -6 3

6

10
573 -1339 899 939 -26 1430 1324 -1150 1640 -45 

1625

提示

【样例解释 #1】

考虑重排为 $-6,-4,5,7,3$，最终的 $f_n$ 为 $6$，可以证明不存在更优的方案。

【数据范围】

本题采用捆绑测试。

• Subtask 0（6 pts）：$n\le10$。
• Subtask 1（14 pts）：$n\le 20$，$|a_i|\le10$。
• Subtask 2（8 pts）：$a$ 中全为正数或全为负数。
• Subtask 3（19 pts）：$a$ 中有且只有一个正数（注意 $a$ 中可以有 $0$）。
• Subtask 4（29 pts）：$n \le 200$，$|a_i|\le 200$。
• Subtask 5（24 pts）：无特殊限制。

对于所有测试数据，$1 \le n \le 2000$，$|a_i|\le 2000$。