5347: Inverse Pair
内存限制：512 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：3
解决：3
题目描述
For a sequence t1...n, we define the weight of it is the number of pairs (i,j) satisfy i<j and ti>tj.
Now give you a permutation a1...n, you need to choose a sequence b1...n satisfies bi∈{0,1} to minimize the weight of sequence c1...n which satisfies ci=ai+bi.
Now give you a permutation a1...n, you need to choose a sequence b1...n satisfies bi∈{0,1} to minimize the weight of sequence c1...n which satisfies ci=ai+bi.
输入
The first line has one integer n.
The second line has n integers a1...n.
It's guaranteed that ai is a permutation of {1,2...n}
1≤n≤2×105
The second line has n integers a1...n.
It's guaranteed that ai is a permutation of {1,2...n}
1≤n≤2×105
输出
Output the minimum weight of c1...n you can get.
样例输入 复制
5
4 3 2 5 1样例输出 复制
5