P10811 [MX-S2-T2] Arrangement.

Original problem link: .

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.

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

Output one integer in one line, representing the answer.

**[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