You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

图书馆里，管理员丽莎·敏兹正面临一项艰巨的任务：整理一批新到的珍贵书籍。这些书籍需要按编号从小到大排列，以便读者快速找到所需的资料。为了确保书籍的安全和保持书架的整洁，丽莎·敏兹只能通过交换相邻书籍来完成任务。

每次交换都需要小心翼翼，因为这些书籍价值连城，稍有不慎就可能损坏。丽莎·敏兹希望尽可能减少交换次数，以提高效率并保护书籍。

管理员丽莎·敏兹需要将书架上的书籍按编号从小到大排序。由于书架设计的限制，丽莎·敏兹只能交换相邻的书籍。若有编号相同且相邻的情况,这些相同且相邻的书籍可任意调换顺序。

你的任务是帮助丽莎·敏兹计算出至少需要多少次相邻书籍的交换，才能完成任务。

Input Format

第一行包含一个整数 $n$ ($1 \leq n \leq 2×10^3$)，表示书籍的数量。

第二行包含 $n$ 个整数 $a_i$ ($1 \leq a_i \leq 10^9$)，表示每本书的编号。

Output Format

输出一个整数，表示至少需要的交换次数。

Sample

输入 #1

4
1 2 3 4

输出 #1

0

输入 #2

3
3 2 1 

输出 #2

3

输入 #3

5
1 3 2 8 2

输出 #3

3

## Hint

一种可行且交换次数最少的整理过程如下:

样例1

1 2 3 4

样例2

3 2 1

3 1 2

1 3 2

1 2 3

样例3

1 3 2 8 2

1 3 2 2 8

1 2 3 2 8

1 2 2 3 8