题目背景

插入排序是一种简单直观的排序算法。它的原理为将待排列元素划分为「已排序」和「未排序」两部分，每次从「未排序的」元素中选择一个插入到「已排序的」元素中的正确位置。

插入排序的平均时间复杂度也是$O(n^2)$，空间复杂度为常数阶$O(1)$，具体时间复杂度和数组的有序性也是有关联的。

插入排序中，当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较 $N-1$ 次，时间复杂度为$O(N)$。最坏的情况是待排序数组是逆序的，此时比较次数最多，最坏的情况是 $O(n^2)$。

在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

题目描述

给定 $n$ 个未排序的数据元素$a_1, a_2, \cdots ,a_n$，使用选择排序进行升序排列。

输出比较次数。

输入格式

第1行一个正整数 $n$

第2行 $n$ 个正整数, 以空格分隔

输出格式

一个正整数，插入排序中交换数据次数。

5
1 2 3 4 5

0

5
1 3 4 2 5

2

5
5 4 3 2 1

10

说明/提示

$1 \le n \le 5*10^3$, $1 \le a_i \le 10^4$