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.

Jeff and Permutation

Examples