You are given a sequence 𝑎1,𝑎2,…,𝑎𝑛, consisting of integers.

You can apply the following operation to this sequence: choose some integer 𝑥 and move all elements equal to 𝑥 either to the beginning, or to the end of 𝑎. Note that you have to move all these elements in one direction in one operation.

For example, if 𝑎=[2,1,3,1,1,3,2], you can get the following sequences in one operation (for convenience, denote elements equal to 𝑥 as 𝑥-elements):

[1,1,1,2,3,3,2] if you move all 1-elements to the beginning;
[2,3,3,2,1,1,1] if you move all 1-elements to the end;
[2,2,1,3,1,1,3] if you move all 2-elements to the beginning;
[1,3,1,1,3,2,2] if you move all 2-elements to the end;
[3,3,2,1,1,1,2] if you move all 3-elements to the beginning;
[2,1,1,1,2,3,3] if you move all 3-elements to the end;
You have to determine the minimum number of such operations so that the sequence 𝑎 becomes sorted in non-descending order. Non-descending order means that for all 𝑖 from 2 to 𝑛, the condition 𝑎𝑖−1≤𝑎𝑖 is satisfied.

Note that you have to answer 𝑞 independent queries.

#### 链接🔗

「CodeForces 1241D」Sequence Sorting

#### 代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <map>
#include <iostream>
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
const int maxd = 2e5+10;
typedef long long ll;
int main()
{
//    freopen("a.in","r",stdin);
//    freopen("k.out","w",stdout);
int t;scanf("%d",&t);
while(t--)
{
int n;scanf("%d",&n);

vector<int> a(n),b(n);
map<int,int> mp;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
b[i] = a[i];
}
sort(all(b));
b.erase(unique(all(b)),b.end());
int m =b.size();
vector<int> l(m),r(m),dp(m);

for(int i=0;i<m;i++) mp[b[i]] = i;
for(int i=0;i<n;i++) r[mp[a[i]]] = i;
for(int i=n-1;i>=0;i--) l[mp[a[i]]] = i;
//for(int i=0;i<m;i++) printf("%d %d\n",l[i],r[i]);
for(int i=0;i<m;i++) dp[i] = 1;
int ans = 1;
for(int i=1;i<m;i++)
{
if(r[i-1] < l[i]) dp[i] = dp[i-1] +1;
ans = max(dp[i],ans);
}
printf("%d\n",m-ans);

}

return 0;
}