题目内容

小红是一个学生，他最近学习的时候遇到了一个题目，题目给定了一个长度为 $n$ 的排列吗，题目要求将这个排列的前 $k$ 个数排列成一个长度为 $k$ 的排列，但是题目规定只能进行相邻两个数的交换操作，题目问最少需要多少次上述操作才能满足题目要求？

小红思考了很久还是不会，他现在想请教你，想让你帮忙解决一下这个问题。

长度为 $n$ 的排列指 $1$ 到 $n$ 中每个数都恰好出现 $1$ 次。例如 $[2,3,1]$ 是排列， $[2,3,4]$ 则不是排列。

输入描述

第一行输入两个正整数 $n$ 和 $k$ 。

第二行输入 $n$ 个正整数 $a_i$ ，代表小红拿到的排列。

$1\le k\le n\le 200000$

$1\le a_i\le n$

输出描述

一个整数，代表最小的操作次数。

样例

输入

5 3
2 4 1 3 5

输出

2

样例解释

第一次交换 $4$ 和 $1$ ，数组变成 $[2,1,4,3,5]$ 。

第二次交换 $4$ 和 $3$ ，数组变成 $[2,1,3,4,5]$ 。

此时前 $3$ 个数构成排列，满足条件。

思路：贪心

解决这个问题的关键在于如何选择交换哪两个数，我们可以观察到，为了最小化交换操作的次数，我们应该优先将大于$k$的数移出前$k$个数，同时将1到$k$的数移入前$k$个数。

由于本题只能交换相邻两个数字，因此，我们可以首先找出前$k$个数中大于$k$的数的位置，然后找出后$n-k$个数中1到$k$的数的位置，然后计算这两个位置的差值的绝对值，这个差值就是需要的最少交换次数。

具体实现我们可以使用两个数组去分别记录$[1,k]$的下标和$[k+1,n]$的下标，然后根据上述计算规则去计算