G. Sign Flipping

You are given an array $a_1,a_2,...,a_n$. In one move, you can select an element $a_i$ and flip its sign (that is, perform $a_i:=-a_i$).

Let $\text{diff}([x_1,x_2,...,x_k])$ be the number of distinct elements in an array $x$ of length $k$.

If we perform the aformentioned moves optimally, what is the maximum possible value of:

Note: You do not have to minimize the number of moves.

Input

The first line of input contains a single integer $n$ ($1 \le n \le 3 \cdot 10^5$) — the length of array $a$.

The second line of input contains $n$ integers $a_1,a_2,\ldots,a_n$ ($-10^9 \le a_i \le 10^9$) — the elements of array $a$.

Output

The first line of output contains the maximum possible value of ${\sum} \text{diff}([a_i,a_{i+1},...,a_j])$, after performing the sign flipping operations optimally.

Example 1

stdin

4
1 1 0 -1

stdout

19

Note

If we flip the signs of $a_2$ and $a_4$, the resulting array will be $[1,-1,0,1]$. Therefore:

• $\text{diff}([1])=1$
• $\text{diff}([1,-1])=2$
• $\text{diff}([1,-1,0])=3$
• $\text{diff}([1,-1,0,1])=3$
• $\text{diff}([-1])=1$
• $\text{diff}([-1,0])=2$
• $\text{diff}([-1,0,1])=3$
• $\text{diff}([0])=1$
• $\text{diff}([0,1])=2$
• $\text{diff}([1])=1$

The sum of all $\text{diff}$'s is equal to $1+2+3+3+1+2+3+1+2+1=19$, which is the maximum possible value.

In the second testcase, regardless of how many operations we will perform, $a$ will remain equal to $[0,0,0]$.

Therefore, $\text{diff}([a_i,a_{i+1},...,a_j])$ is equal to $1$, for all $1 \le i \le j \le n$. Since there are $6$ subarrays, the answer is equal to $6 \cdot 1=6$.

Example 2

stdin

3
0 0 0

stdout

6

Example 3

stdin

15
2 -2 0 1 -3 0 0 3 1 -1 -4 0 -1 -2 3

stdout

510