分数: 466 分
问题陈述
高桥决定整理他房间里的书架。
有 N 书在书架上排成一排。这些书形成了一个系列,其中包括所有 N 卷中的卷 1 音量 N,每卷只有一份副本。 i从左边数第一个位置保存音量 A_i.
高桥想要按照卷号的顺序排列书籍。具体来说,他想要 i从左起第一个位置用于保持音量 i.
Takahashi 可以执行以下操作任意次:
- 交换两本相邻的书。即选择一个整数 j (1 \leq j \leq N-1)并在 j从左边算起第一个位置,书在 (j+1)从左边算起第一个位置。
求按卷号顺序排列书籍所需的最少操作数。
约束
- 1 \leq N \leq 2 \times 10^5
- (A_1, A_2, \ldots, A_N) 是一个排列 (1, 2, \ldots, N)
- 所有输入均为整数
输入
N A_1 A_2 \ldots A_N
- 第一行包含一个整数 N 代表图书数量。
- 第二行包含 N 整数 A_1, A_2, \ldots, A_N 以空格分隔,代表书籍当前的排列方式。 A_i 代表放置在该位置的图书的卷号 i从左边算起第一个位置。
输出
在一行上打印按卷号顺序排列书籍所需的最少操作数。
样本输入 1
5 3 1 2 5 4
示例输出 1
3
示例输入 2
8 8 7 6 5 4 3 2 1
示例输出 2
28
示例输入 3
15 2 1 4 3 6 5 8 7 10 9 12 11 14 13 15
示例输出 3
7