B. Nastya and Door_牛客博客

链接：https://codeforces.ml/contest/1341/problem/B

On February 14, Denis decided to give a Valentine to Nastya and did not come up with anything better than to draw a huge red heart on the door of the length kk (k≥3k≥3). Nastya was very confused by this present, so she decided to break the door, throwing it on the mountains.

Mountains are described by a sequence of heights a1,a2,…,ana1,a2,…,an in order from left to right (k≤nk≤n). It is guaranteed that neighboring heights are not equal to each other (that is, ai≠ai+1ai≠ai+1 for all ii from 11 to n−1n−1).

Peaks of mountains on the segment [l,r][l,r] (from ll to rr) are called indexes ii such that l<i<rl<i<r, ai−1<aiai−1<ai and ai>ai+1ai>ai+1. It is worth noting that the boundary indexes ll and rr for the segment are not peaks. For example, if n=8n=8 and a=[3,1,4,1,5,9,2,6]a=[3,1,4,1,5,9,2,6], then the segment [1,8][1,8] has only two peaks (with indexes 33 and 66), and there are no peaks on the segment [3,6][3,6].

To break the door, Nastya throws it to a segment [l,l+k−1][l,l+k−1] of consecutive mountains of length kk (1≤l≤n−k+11≤l≤n−k+1). When the door touches the peaks of the mountains, it breaks into two parts, after that these parts will continue to fall in different halves and also break into pieces when touching the peaks of the mountains, and so on. Formally, the number of parts that the door will break into will be equal to p+1p+1, where pp is the number of peaks on the segment [l,l+k−1][l,l+k−1].

Nastya wants to break it into as many pieces as possible. Help her choose such a segment of mountains [l,l+k−1][l,l+k−1] that the number of peaks on it is maximum. If there are several optimal segments, Nastya wants to find one for which the value ll is minimal.

Formally, you need to choose a segment of mountains [l,l+k−1][l,l+k−1] that has the maximum number of peaks. Among all such segments, you need to find the segment that has the minimum possible value ll.

Input

The first line contains an integer tt (1≤t≤1041≤t≤104) — the number of test cases. Then the descriptions of the test cases follow.

The first line of each test case contains two integers nn and kk (3≤k≤n≤2⋅1053≤k≤n≤2⋅105) — the number of mountains and the length of the door.

The second line of the input data set contains nn integers a1,a2,…,ana1,a2,…,an (0≤ai≤1090≤ai≤109, ai≠ai+1ai≠ai+1) — the heights of mountains.

It is guaranteed that the sum of nn over all the test cases will not exceed 2⋅1052⋅105.

Output

For each test case, output two integers tt and ll — the maximum number of parts that the door can split into, and the left border of the segment of length kk that the door should be reset to.

Example

input

Copy

5
8 6
1 2 4 1 2 4 1 2
5 3
3 2 3 2 1
10 4
4 3 4 3 2 3 2 1 0 1
15 7
3 7 4 8 2 3 4 5 21 2 3 4 2 1 3
7 5
1 2 3 4 5 6 1

output

Copy

Note

In the first example, you need to select a segment of mountains from 22 to 77. In this segment, the indexes 33 and 66 are peaks, so the answer is 33 (only 22 peaks, so the door will break into 33 parts). It is not difficult to notice that the mountain segments [1,6][1,6] and [3,8][3,8] are not suitable since they only have a 11 peak (for the first segment, the 66 index is not a peak, and for the second segment, the 33 index is not a peak).

In the second example, you need to select a segment of mountains from 22 to 44. In this segment, the index 33 is a peak, so the answer is 22 (only 11 peak, so the door will break into 22 parts).

In the third example, you need to select a segment of mountains from 11 to 44. In this segment, the index 33 is a peak, so the answer is 22 (only 11 peak, so the door will break into 22 parts). You can see that on the segments [2,5][2,5], [4,7][4,7] and [5,8][5,8] the number of peaks is also 11, but these segments have a left border greater than the segment [1,4][1,4], so they are not the correct answer.

代码：

#include<bits/stdc++.h>
using namespace std;
long long n,m,k,t,s,min1,max1;
long long a[200001];
long long b[200001];
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n>>k;
		max1=-1;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			b[i]=0;
		}
		b[1]=0;
		s=0;
		for(int i=2;i<=n-1;i++)
		{
			b[i]=s;
			if(a[i]>a[i-1]&&a[i]>a[i+1])
			{
				s++;
			}
			
		}
		b[n]=s;
		//for(int i=1;i<=n;i++)
		//{
		//	cout<<b[i]<<' ';
		//}
		for(int i=1;i<=n-k+1;i++)
		{
			if(max1<b[i+k-1]-b[i+1])
			{
				max1=b[i+k-1]-b[i+1];
				m=i;
			}
		}
		cout<<max1+1<<" "<<m<<endl;
	}
}