E - Organizing the Bookshelf Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君は自分の部屋の本棚を整理することにしました。

本棚には N 冊の本が一列に並んでいます。これらの本は第 1 巻から第 N 巻までの全 N 巻からなるシリーズで、各巻がちょうど1冊ずつあります。現在、左から i 番目の位置には第 A_i 巻の本が置かれています。

高橋君は本を巻の順に並べたいと思っています。具体的には、左から i 番目の位置に第 i 巻の本が置かれている状態にしたいです。

高橋君は次の操作を好きな回数だけ繰り返し行うことができます。

  • 隣り合う2冊の本を入れ替える。すなわち、整数 j （1 \leq j \leq N-1）を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
  • 1 行目には、本の冊数を表す整数 N が与えられる。
  • 2 行目には、現在の本の並び順を表す N 個の整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。A_i は左から i 番目の位置に置かれている本の巻番号を表す。

出力

本を巻の順に並べるために必要な操作回数の最小値を 1 行で出力してください。

入力例 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

Score : 466 pts

Problem Statement

Takahashi has decided to organize the bookshelf in his room.

There are N books lined up in a row on the bookshelf. These books form a series consisting of all N volumes from volume 1 to volume N, with exactly one copy of each volume. Currently, the i-th position from the left holds volume A_i.

Takahashi wants to arrange the books in order of their volume numbers. Specifically, he wants the i-th position from the left to hold volume i.

Takahashi can perform the following operation any number of times:

  • Swap two adjacent books. That is, choose an integer j (1 \leq j \leq N-1) and swap the book at the j-th position from the left with the book at the (j+1)-th position from the left.

Find the minimum number of operations required to arrange the books in order of their volume numbers.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • (A_1, A_2, \ldots, A_N) is a permutation of (1, 2, \ldots, N)
  • All inputs are integers

Input

N
A_1 A_2 \ldots A_N
  • The first line contains an integer N representing the number of books.
  • The second line contains N integers A_1, A_2, \ldots, A_N separated by spaces, representing the current arrangement of the books. A_i represents the volume number of the book placed at the i-th position from the left.

Output

Print the minimum number of operations required to arrange the books in order of their volume numbers, on a single line.

Sample Input 1

5
3 1 2 5 4

Sample Output 1

3

Sample Input 2

8
8 7 6 5 4 3 2 1

Sample Output 2

28

Sample Input 3

15
2 1 4 3 6 5 8 7 10 9 12 11 14 13 15

Sample Output 3

7