（传送门）
Orz zzkksunboy
题意说的很清楚了。 那么可以想到，把所有不符合排序的数字挪到两边，而把有规律的一段序列保留在中间，由于这段序列一定是单调的，而且贪心的想法肯定最长，所以题目变成最长升（要求最长升序列每两项之间差只能为1，不然空缺的数无法插入），答案就是n-最长升序列长度。问题就是求出最长升长度。
开两个数lst和num，num就是当前求出的最长升长度，lst表示上一项在原序列中在哪，如果发现这次位置在上一项的前面，那么就表示接不起来，重新计算num，否则累加成功，num++。
代码
（貌似题目没说是递增还是递减，所以最长升和最长降都刷了一次，也A了，膜拜zzk）
#include<cstdio> using namespace std; int n,pos[500005],ans,lst,num; inline void readi(int &x) { int tot=0,f=1; char ch=getchar(),lst='+'; while ('0'>ch||ch>'9') {lst=ch; ch=getchar();} if (lst=='-') f=-f; while ('0'<=ch&&ch<='9') {tot=tot*10+ch-48; ch=getchar();} x=tot*f; } int main() { freopen("A.in","r",stdin); freopen("A.out","w",stdout); readi(n); for (int i=1,x;i<=n;i++) {readi(x); pos[x]=i;} ans=lst=num=0; for (int i=1;i<=n;i++){ if (pos[i]>lst) num++; else num=1; lst=pos[i]; if (num>ans) ans=num; } lst=num=0; for (int i=n;i>=1;i--){ if (pos[i]<lst) num++; else num=1; lst=pos[i]; if (num>ans) ans=num; } printf("%d\n",n-ans); return 0; }