题目描述

有 $n$ 个整数 $a_1,a_2,\cdots,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

样例 1 解释

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

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

1625

数据范围

本题采用捆绑测试。

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

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