← 返回题目列表

AtCoder · awc0008_e

E. 整理书架

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

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