[贪心][二分]Sort Zero Codeforces1712C

You are given an array of nn positive integers a1,a2,…,ana1,a2,…,an.

In one operation you do the following:

1. Choose any integer xx.
2. For all ii such that ai=xai=x, do ai:=0ai:=0 (assign 00 to aiai).

Find the minimum number of operations required to sort the array in non-decreasing order.

Input

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤1041≤t≤104). Description of the test cases follows.

The first line of each test case contains a single integer nn (1≤n≤1051≤n≤105).

The second line of each test case contains nn positive integers a1,a2,…,ana1,a2,…,an (1≤ai≤n1≤ai≤n).

It is guaranteed that the sum of nn over all test cases does not exceed 105105.

Output

For each test case print one integer — the minimum number of operations required to sort the array in non-decreasing order.

Example

input

5

3

3 3 2

4

1 3 1 3

5

4 1 5 3 2

4

2 4 1 2

1

1

output

1

2

4

3

0

Note

In the first test case, you can choose x=3x=3 for the operation, the resulting array is [0,0,2][0,0,2].

In the second test case, you can choose x=1x=1 for the first operation and x=3x=3 for the second operation, the resulting array is [0,0,0,0][0,0,0,0].

题意： 给出一个数组，你可以进行若干次操作，每次操作可以选择数组中某个数字x，令所有的x变成0，如果想得到一个不减序列的最少操作次数是多少。

分析： 操作次数满足二分性质，所以可以尝试一下二分，在check(x)函数中需要判断能否通过至多x次操作得到不减序列，那具体选哪几个数变成0呢？贪心地想，选择最靠前的非0数字最优，这是因为假如选择的是中间的非0数字，那么为了序列整体不减，前面的非0数字也一定要变成0，这样至少也要操作两次，但是直接选择最靠前的非0数字一定不会比这种方案差，毕竟它可以之后再选择中间的非0数字，甚至还会更优，因为这样是至少操作一次。所以贪心策略就是操作机会都用在最靠前的非0数字上，最后检查一下序列是否不减，最终复杂度为O(nlogn)。

具体代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
 
int a[100005], n, cpy[100005];
 
bool check(int x){
	unordered_map<int, bool> mp;
	for(int i = 1; i <= n; i++){
		if(mp.count(cpy[i]))
			cpy[i] = 0;
		else if(mp.size() < x){
			mp[cpy[i]] = true;
			cpy[i] = 0;
		}
	}
	for(int i = 2; i <= n; i++)
		if(cpy[i]-cpy[i-1] < 0) return false;
	return true;
}
 
signed main()
{
	int T;
	cin >> T;
	while(T--){
		scanf("%d", &n);
		for(int i = 1; i <= n; i++)
			scanf("%d", &a[i]);
		int l = 0, r = n, ans = -1;
		while(l <= r){
			for(int i = 1; i <= n; i++)
				cpy[i] = a[i];
			int mid = l+r>>1;
			if(check(mid)){
				ans = mid;
				r = mid-1;
			}
			else l = mid+1;
		}
		printf("%d\n", ans);
	} 
    return 0;
}