404517: GYM101522 I Inverted Signs

Arya lives in a magical world. You can view it as a number line.

There are N citizens in total. The i-th citizen have his own house in position i with height H_i, Noted that H_i could be non positive, which means their house is actually built beneath the horizon.

Arya is the hand of the king and she thinks that the buildings are a bit out of order. She denote the chaos index of the world as .

Noted that h_i could be equal to zero as the world is magical.

She feels that the current chaos index of the world is too high. So she designs to change the world a bit by using her super power.

She could flip a continuous sequence of building, i.e., she could choose two arbitrary integer L and R, where 1 ≤ L ≤ R ≤ N, and invert the signs of H_i for all L ≤ i ≤ R (positive to negative and vice versa).

As Arya is weak, she would only do this operation exactly once. Arya wants to minimize the chaos index after the operation. Being a good guy, help Arya to find the lowest possible chaos index after exactly flipping one continuous sequence of building.

The first line contains an integer N. (1 ≤ N ≤ 10⁶)

The second line consist of N integers, the i-th integer is H_i. ( - 10⁹ ≤ H_i ≤ 10⁹)

Output consist only one integer in a single line, the lowest possible chaos index after exactly flipping one continuous sequence of building.

4
1 -2 -3 4

3

5
-3 -2 0 -5 3

10

In the first sample, Arya should flip house 2 to 3, so that the heights become 1, 2, 3, 4 and the chaos index would be |2 - 1| + |3 - 2| + |4 - 3| = 3.

|x - y| is the absolute difference between x and y.