F2. Flying Sort
题意：给定n个数，n个数可能有相同的，每次操作只能选择一个数，将它放在这个数组的首位或者尾部，询问你最少需要进行多少次操作能够让这个数组非递减。
题解：首先离散化一下，然后定义dp[i]代表全选a[i]的最长子序列的长度，定义子序列：子序列之外的元素都大于等于子序列的尾部或者小于等于子序列的首部。这里讲一下这个题的细节部分：就是你单纯看定义的子序列，你会发现这个子序列最大值和最小值相差1，你一定能想到，但是如果不是相差1，你需要考虑的就是全选首部或者尾部或者中间的，这就是dp[i]为什么要定义为全选a[i]。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int a[maxn] , b[maxn];
vector<int>G[maxn];
int dp[maxn];
int main()
{int t; scanf("%d",&t);while(t--){int n; scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);b[i] = a[i];G[i].clear();}sort(b+1,b+1+n);int sz = unique(b+1,b+1+n) - b - 1;for(int i=1;i<=n;i++){int p = lower_bound(b+1,b+1+sz,a[i]) - b ;G[p].push_back(i);}int ans = 0;for(int i=1;i<=sz;i++){dp[i] = G[i].size();if(G[i-1].size()&&G[i-1][G[i-1].size()-1]<G[i][0])dp[i] = max(dp[i],dp[i-1]+(int)G[i].size());int cnt =  0;for(auto tmp:G[i-1]) if(tmp<G[i][0]) cnt++;dp[i] = max(dp[i],(int)G[i].size()+cnt);cnt = 0;for(auto tmp:G[i]) if(G[i-1].size()&&tmp>G[i-1][G[i-1].size()-1]) cnt++;ans = max(ans,dp[i-1]+cnt);if(G[i-1].size()){for(int j=0;j<G[i-1].size();j++){int cnt = 0;for(auto tmp:G[i]) if(tmp>G[i-1][j]) cnt++;ans = max(ans,j+1+cnt);}}}for(int i=1;i<=sz;i++) ans = max(ans,dp[i]);printf("%d\n",n-ans);}
}