Jeff and Permutation

2000ms

262144K

Description:

Jeff's friends know full well that the boy likes to get sequences and arrays for his birthday. Thus, Jeff got sequence p₁, p₂, ..., p_n for his birthday.

Jeff hates inversions in sequences. An inversion in sequence a₁, a₂, ..., 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.

Input:

The first line contains integer n (1 ≤ n ≤ 2000). The next line contains n integers — sequence p₁, p₂, ..., p_n (|p_i| ≤ 10⁵). The numbers are separated by spaces.

Output:

In a single line print the answer to the problem — the minimum number of inversions Jeff can get.

Sample Input:

2
2 1

Sample Output:

Sample Input:

9
-2 0 -1 0 -1 2 1 0 -1

Sample Output:

Informação

Provedor Codeforces

Código CF351E