Description

Jeff’s friends know full well that the boy likes to get sequences and arrays for his birthday. Thus, Jeff got sequence $p_1,p_2,\cdots,p_n$ for his birthday.

Jeff hates inversions in sequences. An inversion in sequence $a_1, a_2,\cdots,a_n$ is a pair of indexes $i,j (1 ≤ i <  j ≤ n)$, such that an inequality $a_i>a_j$ holds.

Jeff can multiply some numbers of the sequence $p$ by $-1$. At that, he wants the number of inversions in the sequence to be minimum. Help Jeff and find the minimum number of inversions he manages to get.

Idea

Considering a number pair $(a_i,a_j)$. If $|a_i|=|a_j|$, there won’t be a inversion definitely. If the case is $|a_i|<|a_j|$, whether a inversion exists will be determined directly by whether $a_j$ is positive or negative.

It turns out that for each $a_i$, let $A$ be the number bigger than it before, and $B$ be the ones after it. The minimum answer is $\sum \min (A_i,B_i).$ 

Code