Jeff 的朋友们非常清楚,这个男孩喜欢在生日时收到序列和数组。因此,Jeff 得到了他生日的序列 p1, p2, ..., pn。
Jeff 讨厌序列中的反转。序列 a1, a2, ..., an 中的反转是一对索引 i, j (1 ≤ i < j ≤ n),因此不等式 ai > aj 成立。
Jeff 可以将序列 p 的某些数字乘以 -1。此时,他希望序列中的反转次数最少。帮助杰夫找出他能做到的最少倒转次数。
输入
第一行包含整数 n (1 ≤ n ≤ 2000)。下一行包含 n 个整数 — 序列 p1, p2, ..., pn (|pi| ≤ 105)。数字之间用空格分隔。
输出
在一行中打印问题的答案 - Jeff 可以获得的最小反转次数。
示例
输入 #1
2 2 1
输出 #1
0
输入 #2
9 -2 0 -1 0 -1 2 1 0 -1
输出 #2
6