<span>codeforces 1367 F1，F2 Flying Sort</span>

题意

给出一个长度为\(n\)的数组\(a\)，每次操作能将一个数移动到数组的首位或末尾，问最少经过多少次操作能将这个数组变成单调不降的。

分析

在\(F_1\)中数组\(a\)的每个数字互不相同，我们发现只要找到最长的连续上升子序列（连续指在数组排序后两个数字是相邻的），n减去它的长度\(len\)即为答案，因为这个序列是有序的，只需要\(n-len\)次操作将其他位置的数移动到这个序列的两边使数组整体有序即可。

在\(F_2\)中数组\(a\)中可能会有相同的数字，我们可以用近似的方式去做，找到一个最长的连续不降子序列且除了首尾的数字，和序列中的其他数字相同的数字都要在这个子序列中，这样就能保证只用\(n-len\)次操作将其他位置的数移动到这个序列的两边使数组整体有序。

例如序列\(1,2,3,2,4,3\)，我们能找到\(1,2,2,3\)这个符合要求的最长连续不降子序列，但是不能选择\(1,2,3,4\)这个子序列，因为不能把剩下的2和3移动到这个序列的两边，而选择\(1,2,2,3\)这个子序列，你可以将剩下的3和4依次移动到数组的末尾。

用\(dp\)找到一个最长的符合条件的子序列即可。

Code

#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<sstream>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#include<map>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define per(i,n,x) for(int i=n;i>=x;i--)
#define sz(a) int(a.size())
#define rson mid+1,r,p<<1|1
#define pii pair<int,int>
#define lson l,mid,p<<1
#define ll long long
#define pb push_back
#define mp make_pair
#define se second
#define fi first
using namespace std;
const double eps=1e-8;
const int mod=1e9+7;
const int N=2e5+10;
const int inf=1e9;
int t,n,a[N],b[N],f[N],l[N],r[N],cnt[N],c[N];
int main(){
	ios::sync_with_stdio(false);
	//freopen("in","r",stdin);
	cin>>t;
	rep(cas,1,t){
		cin>>n;
		rep(i,1,n){
			cin>>a[i];
			b[i]=a[i];
			f[i]=cnt[i]=c[i]=0;
			l[i]=inf;
		}
		sort(b+1,b+n+1);
		int m=unique(b+1,b+n+1)-b-1;
		rep(i,1,n){
			a[i]=lower_bound(b+1,b+m+1,a[i])-b;
			l[a[i]]=min(l[a[i]],i);
			r[a[i]]=i;
			c[a[i]]++;
		}
		int ans=0;
		rep(i,1,n){
			int tmp=0;
			if(l[a[i]]==i&&r[a[i]-1]<i) tmp=max(tmp,f[a[i]-1]+1);
			if(l[a[i]]==i) tmp=max(tmp,cnt[a[i]-1]+1);
			tmp=max(tmp,f[a[i]]+1);
			f[a[i]]=tmp;
			if(r[a[i]-1]<i){
				tmp=max(tmp,f[a[i]-1]+c[a[i]]);
				ans=max(ans,tmp);
			}else{
				ans=max(ans,cnt[a[i]-1]+c[a[i]]);
			}
			cnt[a[i]]++;
			c[a[i]]--;
		}
		cout<<n-ans<<'\n';
	}
	return 0;
}