G. Sign Flipping

Time limit: 1s Memory limit: 256MB Input: Output:

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

Let diff([x1,x2,...,xk])\text{diff}([x_1,x_2,...,x_k]) be the number of distinct elements in an array xx of length kk.

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

i=1nj=indiff([ai,ai+1,...,aj])\sum_{i=1}^n\sum_{j=i}^n \text{diff}([a_i,a_{i+1},...,a_j])

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

Input

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

The second line of input contains nn integers a1,a2,,ana_1,a_2,\ldots,a_n (109ai109-10^9 \le a_i \le 10^9) — the elements of array aa.

Output

The first line of output contains the maximum possible value of diff([ai,ai+1,...,aj]){\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 a2a_2 and a4a_4, the resulting array will be [1,1,0,1][1,-1,0,1]. Therefore:

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

The sum of all diff\text{diff}'s is equal to 1+2+3+3+1+2+3+1+2+1=191+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, aa will remain equal to [0,0,0][0,0,0].

Therefore, diff([ai,ai+1,...,aj])\text{diff}([a_i,a_{i+1},...,a_j]) is equal to 11, for all 1ijn1 \le i \le j \le n. Since there are 66 subarrays, the answer is equal to 61=66 \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

Log in or sign up to be able to send submissions!