分数: 2000 点
问题陈述
给你一个排列 P=(P_1,P_2,\cdots,P_N) of (1,2,\cdots,N).
您想要对相邻元素执行零次或多次交换,以便 P 满足以下条件:
- 索引数量 i 这样 P_i > P_{i+1} 最多是 1.
找出所需的最小交换次数。
约束
- 2 \leq N \leq 800000
- (P_1,P_2,\cdots,P_N) 是一个排列 (1,2,\cdots,N).
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N P_1 P_2 \cdots P_N
输出
打印答案。
示例输入 1
3 3 2 1
示例输出 1
1
交换 P_1 和 P_2 转 P 进入 (2,3,1),满足条件。
示例输入 2
4 2 4 1 3
示例输出 2
0
示例输入 3
6 2 3 1 6 4 5
示例输出 3
1
示例输入 4
20 8 13 6 11 20 3 12 18 17 4 10 1 7 16 19 5 2 15 14 9
示例输出 4
36