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:
$$$$$$\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.
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$$$.
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.
4 1 1 0 -1
19
3 0 0 0
6
15 2 -2 0 1 -3 0 0 3 1 -1 -4 0 -1 -2 3
510
In the first testcase, if we flip the signs of $$$a_2$$$ and $$$a_4$$$, the resulting array will be $$$[1,-1,0,1]$$$. Therefore:
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$$$.
| RCPCamp 2023 Day 1 |
|---|
| Finished |
