All submissions for this problem are available.
You are in the city’s municipal office and now have some construction work to do. The city has n towers arranged in a street. You know the height of each tower. But because the adjacent towers are of different heights, the city looks ugly. The corporation has asked you to beautify the city.
The city can be made more beautiful by making the adjacent towers of the same height. Being a programmer, you have some unusual powers at hand. You can demolish some existing building and then shift the other buildings so that to close in the gap created by destroying the building. (You can assume that all towers are of same width). But you are not God and have some limitations. You can do the above operation at most k times. Given the heights of the buildings you need to find out the maximum number of adjacent towers you can have that are of the same height.
The first line of input consists of the number of test cases T. Then T lines follow each describing a test case. The first line of each test case consists of two numbers n and k. The next line consists of n numbers denoting the height of the towers. All numbers are space separated.
For each test case print a line denoting the maximum number of adjacent towers of the same height you can make by using your powers.
1≤ n ≤ 105
0 ≤ k < n
1≤ height of each tower ≤ 105
Input: 2 6 1 3 4 5 3 4 5 4 0 3 3 4 4 Output: 1 2
|Time Limit:||1.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, GO|
Fetching successful submissions
If you are still having problems, see a sample solution here.