Jeff and Permutation

题意翻译

给出数组a ,你可以改变每个数的正负，求逆序对数最少是多少 翻译贡献者UID：35873

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

2
2 1

输出样例 #1

0

输入样例 #2

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

输出样例 #2

6