← 返回题目列表

AtCoder · awtf2024_d

D. 几乎是冒泡排序

中文机器翻译题面 查看原题

分数: 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