一道诈骗题，英语课上一直在想然后想出来了（
正难则反，我们很难按照题目所说的得到最少步数，可以考虑从排好序的状态开始。
这样，每次就从首或尾中选择一个移到任意一个位置了，简单了些。
（因为我们只能移动首尾，当前移动到哪里最优貌似可以贪心）
所以下面令初始状态为有序的那个，目标状态为初始时给定的那个。
接着，移动完成的目标就是初始的数组，不是很能看出来，也不太好搞，就再化简了一些。
按照题目所说，给的排列是 $p_1,p_2,p_3\cdots p_n$，我们令 $loc[p_i]=i$。
把初始状态中的每个数 $x$ 换成 $loc[x]$，初始数组变为 $loc[1],loc[2]\cdots loc[n]$。
显然，这不会影响答案，因为我们接着再把 $p_i$ 换成 $loc[p_i]$ 即 $i$，（因为交换两个数等于把这两个数在目标数组中的位置互换）。
经过一番转换后，目标数组变成了有序的而初始无序了，操作变为首尾选一个放到任意位置的最少操作次数。
考虑这个问题如何求解，这是一个简单的贪心了。找到目标数组中的 最大连续上升序列，答案即为 $n-$ 它的大小。
为什么呢？我们可以把它前面后面的都移到正确的位置，而最大连续上升序列就不需要动了，严谨的证明我不会，全靠猜的（
代码很短，和拼接单词差不多了:）：（甲组 T1 线段树打表简单不讲，T2 OEIS 乱搞，T3 插头 DP 值得一讲）
#include <iostream> using namespace std; int n, x, ans, cnt; int loc[100005]; int main () { cin >> n; for (int i = 1; i <= n; i ++) { cin >> x; loc[x] = i; } for (int i = 1; i <= n; i ++) { if (i == 1 || loc[i] > loc[i - 1]) ++ cnt; else { ans = max (ans, cnt); cnt = 1; } } ans = max (ans, cnt); cout << n - ans; return 0; }