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}, ..., *p*_{*n*}$ for his birthday.

Jeff hates inversions in sequences. An inversion in sequence $*a*_{1}, *a*_{2}, ..., *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*_{1}$, $*p*_{2}$, $...$, $*p*_{*n*}$ $(|*p*_{*i*}| ≤ 10^{5})$. 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.