思路：排序+双指针

其实就是找到一段连续的数值，有点类似 LeetCode 2134，就是多了一个排序的过程，比如[1,5]这个区间，中间隔了3个数字，那么就需要执行3个操作，才可以保证这个区间是一个连续的区间，对应的操作次数就是n-(r-l+1)，如果区间所需要的数字比n还大，说明不满足条件，需要l指针右移。

代码

题目内容

小红 $4*10^9+1$ 个羊圈，这些羊圈的编号依次为 $-2*10^9～2*10^9$，有的羊圈有若干只羊，有的是空羊圈。现在，小红想将一些羊圈中的羊赶入某些羊圈杯中，以此来重新排列这些羊圈的次序。最终让所有的羊最终都圈在 $n$ 个不同的羊圈中，并且这 $n$ 个羊圈编号依次相邻。为了防止羊羊逃跑，对于每一次转移，小红只能将任何一个羊圈中的所有羊全部赶入任何一个空的羊圈中。

求最少的转移次数？

输入描述

第一行输入有羊的羊圈的数量 $N$。

随后 $N$ 行，输入N个有羊的羊圈的编号 $a_i$。

保证没有两个 $a_i$是相同的。

$1\leqslant N\leqslant 10^5$

$-2*10^9\leqslant a_i\leqslant 2*10^9$

输出描述

输出羊的最少的转移次数使得有羊的羊圈按照顺序排列。

样例

样例1

输入

4
13 12 11 14

输出

0

样例解释

现在，在11,12,13,14号羊圈中有羊羊了，所以不需要调整了。

样例2

输入

5
2 0 -1 3 6

输出

1	

样例解释

现在在-1,0,2,3,6中有羊，因此，1号羊圈没有羊，因此可以将6号羊圈中的羊全部赶入1号羊圈中，这样有羊的羊圈为-1,0,1,2,3

样例1

输入

5
2 -4 -1 3 6

输出

2

样例解释

现在在-4,1,2,3,6中有羊，可以将-4号羊圈中的羊赶入入0号羊圈，将6号羊圈中的羊赶入1号羊圈，这样，-1,0,1,2,3均有羊。