Problem Description

Given \( n \) integers \( a_1, a_2, \ldots, a_n \). Define \( f_0 = 0 \) and \( f_i \) as follows:
\[ f_i = \begin{cases} f_{i-1} & \text{if } f_{i-1} \times a_i > 0, \\ f_{i-1} + a_i & \text{if } f_{i-1} \times a_i \le 0. \end{cases} \]

Rearrange \( a \) to maximize \( f_n \).

Input Format

The first line contains an integer \( n \).

The second line contains \( n \) integers \( a_1, \ldots, a_n \).

Output Format

Output a single integer, the maximum possible value of \( f_n \).

Sample Input and Output

Sample Input #1

5
7 5 -4 -6 3

Sample Output #1

6

Sample Input #2

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

Sample Output #2

1625

Notes

[Sample Explanation #1]

Consider rearranging to \(-6, -4, 5, 7, 3\), resulting in \( f_n = 6 \). It can be proven that no better arrangement exists.

[Data Range]

This problem uses batched testing.

• Subtask 0 (6 pts): \( n \le 10 \).
• Subtask 1 (14 pts): \( n \le 20 \), \( |a_i| \le 10 \).
• Subtask 2 (8 pts): All \( a \) are either all positive or all negative.
• Subtask 3 (19 pts): There is exactly one positive number in \( a \) (note that \( a \) can contain zeros).
• Subtask 4 (29 pts): \( n \le 200 \), \( |a_i| \le 200 \).
• Subtask 5 (24 pts): No special restrictions.

For all test cases, \( 1 \le n \le 2000 \), \( |a_i| \le 2000 \).

见题面 Input 部分

见题面 Output 部分