B. Moamen and k-subarrays（codeforce+二分查找）

B. Moamen and k-subarrays

time limit per test2 seconds

memory limit per test256 megabytes

inputstandard input

outputstandard output

Moamen has an array of n distinct integers. He wants to sort that array in non-decreasing order by doing the following operations in order exactly once:

Split the array into exactly k non-empty subarrays such that each element belongs to exactly one subarray.

Reorder these subarrays arbitrary.

Merge the subarrays in their new order.

A sequence a is a subarray of a sequence b if a can be obtained from b by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Can you tell Moamen if there is a way to sort the array in non-decreasing order using the operations written above?

Input

The first line contains a single integer t (1≤t≤103) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers n and k (1≤k≤n≤105).

The second line contains n integers a1,a2,…,an (0≤|ai|≤109). It is guaranteed that all numbers are distinct.

It is guaranteed that the sum of n over all test cases does not exceed 3⋅105.

Output

For each test case, you should output a single string.

If Moamen can sort the array in non-decreasing order, output “YES” (without quotes). Otherwise, output “NO” (without quotes).

You can print each letter of “YES” and “NO” in any case (upper or lower).

Example

inputCopy

3

5 4

6 3 4 2 1

4 2

1 -4 0 -2

5 1

1 2 3 4 5

outputCopy

Yes

No

Yes

Note

In the first test case, a=[6,3,4,2,1], and k=4, so we can do the operations as follows:

Split a into {[6],[3,4],[2],[1]}.

Reorder them: {[1],[2],[3,4],[6]}.

Merge them: [1,2,3,4,6], so now the array is sorted.

In the second test case, there is no way to sort the array by splitting it into only 2 subarrays.

As an example, if we split it into {[1,−4],[0,−2]}, we can reorder them into {[1,−4],[0,−2]} or {[0,−2],[1,−4]}. However, after merging the subarrays, it is impossible to get a sorted array.

#include <iostream>
#include <queue>
#include<algorithm>
#include<cstdio>
#include<deque>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<map>
#include<list>
#include<cstring>
#include<string>
#include<cstdlib>
#include<bitset>
#include<cmath>
const long long inf=1e9+10;
using namespace std;
int a[100005],b[100005],c[100005];
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,k;
		cin>>n>>k;
		int sum=1;
	
		for(int i=0;i<n;i++)
		{
			cin>>a[i];
			b[i]=a[i];
		}
		
		sort(b,b+n);
		for(int i=0;i<n;i++)
		{
			c[i]=lower_bound(b,b+n,a[i])-b;//二分查找，大于等于
			 //c[i]=upper_bound(b,b+n,a[i])-b;//大于 
		}
		for(int i=1;i<n;i++)
		{
			if(c[i]!=c[i-1]+1)
			sum++;
		}
		//cout<<sum<<"..";
		if(k>=sum)
		cout<<"Yes"<<endl;
		else
		cout<<"No"<<endl;
	}
    return 0;
}