You are playing a game with array $A$ of $n$ integers consisting of only 3 values $-1, 0, 1$.
You can choose an arbitrary integer in the range $[1, n]$ and your score the larger one of the 2 following expressions:
$$(A_1 + A_2 + ... + A_i) \times (-1) + (A_{i + 1} + ... + A_n)$$
or
$$(A_1 + A_2 + ... + A_i) + (A_{i + 1} + ... + A_n) \times (-1) $$
Find a way to achieve maximum score.
### Input
- The first line contains an integer $n$.
- The second line contains $n$ integers $A_i$.
### Output
- Maximum possible score.
### Constraints
- $1 \le n \le 10^5$.
- $A_i \in \\{-1, 0, 1\\}$.
### Example
Input:
```
4
1 1 1 -1
```
Output:
```
4
```
