【题目描述】

小 $\psi$ 是来自半人马座的外星人。

他有 $n$ 台飞碟，从 $1$ 到 $n$ 编号，这 $n$ 台飞碟停在 $n$ 个位置上，每个位置也从 $1$ 到 $n$ 编号。现在每一个位置恰好停着一台飞碟，对于所有 $1\leq i\leq n$，在第 $i$ 个位置上停放的飞碟编号为 $p_i$。

由于飞碟摆放的位置杂乱无章，于是小 $\psi$ 想要通过一些操作让这些飞碟摆放的位置变得更加的有序。每一次操作，小 $\psi$ 可以选择两个满足 $|i-j|=1$ 的位置 $i,j$，将位置 $i$ 上的飞碟与位置 $j$ 上的飞碟交换。

现在小 $\psi$ 想要通过若干次操作使得飞碟的摆放满足如下条件：

• 至多存在一个在 $[1,n-1]$ 中的整数 $i$，满足位置 $i$ 停放的飞碟编号大于位置 $i+1$ 停放的飞碟编号。特殊的，如果不存在这样的 $i$，也视为满足条件。

小 $\psi$ 想知道他至少要通过多少次操作才使得飞碟的摆放满足上述条件呢，如果你能解决这个问题，他将会给你一张参加半人马座程序设计竞赛的门票。

【输入格式】

从文件 ufo.in 中读入数据。

输入的第一行包含两个非负整数 $c,n$，分别表示测试点编号与飞碟个数。特别的，样例的 $c$ 表示该样例与编号为 $c$ 的测试点的约束条件相同。

接下来一行包含 $n$ 个正整数，其中第 $i$ 个数表示第 $i$ 个位置停放的飞碟的编号，保证给出的 $n$ 个正整数均在 $[1,n]$ 之间，且互不相同。

【输出格式】

输出到文件 ufo.out 中。

输出一行一个整数表示至少要进行多少次操作才能够使得飞碟的摆放满足小 $\psi$ 给出的条件。

【样例输入1】

1 6
2 3 1 6 4 5

【样例输出1】

1

【样例解释1】

对位置 $3$ 的飞碟与位置 $4$ 的飞碟进行交换，则 $n$ 个位置的飞碟按位置从小到大所对应的编号依次为 $2\;3\;6\;1\;4\;5$，此时不难验证飞碟的摆放满足小 $\psi$ 给出的条件。

【样例输入2】

1 20
8 13 6 11 20 3 12 18 17 4 10 1 7 16 19 5 2 15 14 9

【样例输出2】

36

【样例输入/输出3】

见选手目录下的 ufo3.in/ans，该样例满足测试点 $3$ 的限制。

【样例输入/输出4】

见选手目录下的 ufo4.in/ans，该样例满足测试点 $9$ 的限制。

【样例输入/输出5】

见选手目录下的 ufo5.in/ans，该样例满足测试点 $15$ 的限制。

【测试点约束】

对于所有测试数据，满足：

• $2\leq n\leq 3\times 10^6$；
• 保证给出的 $n$ 个位置停放的飞碟编号互不相同，且均为 $[1,n]$ 之间的正整数。

每个测试点的具体限制如下表：

测试点编号	$n\le$	特殊性质
$1\sim 2$	$20$	无
$3\sim 5$	$600$
$6\sim 8$	$5000$
$9\sim 12$	$10^5$	A
$13\sim 14$		无
$15\sim 17$	$5\times 10^5$
$18\sim 20$	$3\times 10^6$

特殊性质 A：对于所有 $1\leq i\leq n$，位置 $i$ 停放的飞碟编号在 $[i-10,i+10]$ 之间。

samples