题目描述

一个数组的元素为 $1$ 至 $N$ 的整数，现在要对这个数组进行排序，在排序时只能将元素放在数组的头部或尾部，问至少需要移动多少个数字，才能完成整个排序过程？

输入格式

第一行一个数 $N\ (2 \le N \le 10^5)$。

第二行 $N$ 个数 $a_i$，表示原始数组元素。

输出格式

输出一个整数表示答案。

5
4 1 2 5 3

2

• 操作 $1$：将 $\tt 5$ 和 $\tt 3$ 换一下变成 $\texttt{4 1 2 3 5}$；
• 操作 $2$：将 $\texttt{1 2 3}$ 和 $\tt 4$ 换一下变成 $\texttt{1 2 3 4 5}$ 在此后即完成要求。

所以最小操作次数为 $2$。

4
4 1 3 2

2