A. Alternating Signs
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$A=[a_1, a_2, ..., a_n]$$$ of $$$n$$$ integers. Find a subsequence $$$a_{i_1}, a_{i_2}, ..., a_{i_k}$$$, such that the sums of elements in that subsequence is maximum possible and the signs of the numbers alternate, i.e. the sign of $$$a_{i_x}$$$ is different from the sign of $$$a_{i_{x+1}}$$$ of all $$$1 \leq x \lt k$$$. Recall that $$$a_{i_1}, a_{i_2}, ..., a_{i_k}$$$ is a subsequence of $$$A$$$ if $$$i_1 \lt i_2 \lt ... \lt i_k$$$.

Note that the subsequence may be empty.

Input

The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) $$$-$$$ length of array A.

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, $$$...$$$, $$$a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$, $$$a_i \neq 0$$$) $$$-$$$ elements of array $$$A$$$.

Output

Print a single integer $$$-$$$ maximum possible sum of elements in a subsequences with given constrains.

Examples
Input
4
7 1 -1 5
Output
11
Input
3
-1 -1 -1
Output
0