其实并不难，官方题解给的 dp 做法太吓人了
题解 #
首先定义一下“排了序的子序列”：它是一个原数组的子序列并且在排序之后的数组中是一个子数组。不难看出没用被移动过的元素会形成一个排了序的子序列。所以说如果我们找到最长的排了序的子序列那么答案就是最小的。
因为我们只关注数字的相对大小，我们可以压缩一下数字，这样写起来会简单一些。然后每个数组开一个数组存改数字的所有下标。
然后遍历所有数字，如果当前数字的最小下标大于之前数字的最大下标，那么这个数字的所有下标都可以加到当前的子序列里。否则我们需要重新开始一个子序列，以下两点需要注意：
-
当前数字的一部分也是可以被加到刚才的子序列里的，比如说
1,2,2,1,2，第二个 2 就可以加进去变成1,1,1,2。 -
之前的数的一部分也可以被加到新的子序列里，比如
1,2,2,1,2，我们可以把第一个 1 加进来变成1,2,2,2。
但是还有一种特殊的情况：这个子序列只包含两个数的下标，并且这两个数的下标都是不完整的，比如2,1,1,2,2,1。不难看出我们要取第一个数的一个前缀，取第二个数的一个后缀，那么我们就可以枚举前缀的位置然后找到对应的后缀。
Code #
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define all(x) (x).begin(),(x).end()
#define size(x) int(x.size())
#define pb push_back
using namespace std;
using ll=long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt;
cin>>tt;
for1(T,tt){
int n;
cin>>n;
vector<int> a(n),d(n);
forn(i,n){
cin>>a[i];
d[i]=a[i];
}
//coord compression
sort(all(d));
d.resize(unique(all(d))-d.begin());
vector<vector<int>> pos(size(d));
forn(i,n){
a[i]=lower_bound(all(d),a[i])-d.begin();
pos[a[i]].push_back(i);
}
int r=-1,mxlen=0,curlen=0;
forn(i,size(d)){
if(pos[i][0]>r){
curlen+=size(pos[i]);
}else{
//extend to the right for the old sequence
auto j=lower_bound(all(pos[i]),r);
mxlen=max(mxlen,curlen+int(pos[i].end()-j));
//extend to the left for the new sequence
auto it=lower_bound(all(pos[i-1]),pos[i][0]);
curlen=int(it-pos[i-1].begin())+size(pos[i]);
}
mxlen=max(mxlen,curlen);
r=pos[i].back();
}
//check the special case: sequence containing only two numbers
forn(i,size(d)-1){
forn(j,size(pos[i])){
auto it=lower_bound(all(pos[i+1]),pos[i][j]);
mxlen=max(mxlen,j+1+int(pos[i+1].end()-it));
}
}
cout<<n-mxlen<<endl;
}
return 0;
}