No tag edit access

E. Jeff and Permutation

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputJeff'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.

Examples

Input

2

2 1

Output

0

Input

9

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

Output

6

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/14/2017 21:46:19 (c5).

Desktop version, switch to mobile version.

User lists

Name |
---|