Background

Original problem link: https://oier.team/problems/S2B.

Problem Description

There are $n$ integers $a_1,a_2,\ldots,a_n$. Let $f_0=0$, and $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.$ Reorder $a$ so that the resulting $f_n$ is maximized.

Input Format

The first line contains one integer $n$.

The second line contains $n$ integers $a_1,\dots,a_n$.

Output Format

Output one integer in one line, representing the answer.

5
7 5 -4 -6 3

6

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

1625

Hint

[Sample Explanation #1]

Consider reordering as $-6,-4,5,7,3$. The final $f_n$ is $6$. It can be proven that there is no better arrangement.

[Constraints]

This problem uses bundled testdata.

• Subtask 0 (6 pts): $n\le10$.
• Subtask 1 (14 pts): $n\le 20$, $|a_i|\le10$.
• Subtask 2 (8 pts): all numbers in $a$ are positive, or all are negative.
• Subtask 3 (19 pts): there is exactly one positive number in $a$ (note that $a$ may contain $0$).
• Subtask 4 (29 pts): $n \le 200$, $|a_i|\le 200$.
• Subtask 5 (24 pts): no special constraints.

For all testdata, $1 \le n \le 2000$, $|a_i|\le 2000$.

Translated by ChatGPT 5