Min Max Equality ~ Multiplex Coder

Chef found an array

A

N

elements. He defines a subarray as bad if the maximum element of the subarray is equal to the minimum element of the subarray.

More formally, a subarray $[L, R]$

(1 \leq L \leq R \leq N)

is bad if

max (A_{L}, A_{L + 1}, \dots, A_{R}) = min (A_{L}, A_{L + 1}, . . ., A_{R})

Chef is allowed to change at most $K$

elements of the array.
Find the minimum number of bad subarrays Chef can obtain after changing at most

K

elements of the array.

, the number of test cases. Then the test cases follow.

Each test case contains two lines of input, the first line contains two space-separated integers

N

and

K

- the number of elements in the array and the maximum number of elements Chef can change respectively.

The second line contains

N

space-separated integers

A_{1}, A_{2}, \dots, A_{N}

For each test case, output the minimum number of bad subarrays Chef can obtain after changing at most $K$

elements of the array.

1 \leq N \leq 10^{5}

1 \leq K \leq N

1 \leq A_{i} \leq 10^{9}

Sum of

N

over all test cases does not exceed

3 \cdot 10^{5}

3
4
7

Test case $1$

: The minimum number of bad subarrays Chef can obtain is

3

. Chef does not need to perform any operations. The subarrays where the maximum element is equal to the minimum element are

[1, 1], [2, 2],

and

[3, 3]

where

[L, R]

denotes the subarray starting at index

L

and ending at index

R

Test case $2$

: The minimum number of bad subarrays Chef can obtain is

4

. Chef can perform

2

operations and change the array to

[2, 4, 3, 1]

. The subarrays where the maximum element is equal to the minimum element are

[1, 1], [2, 2], [3, 3],

and

[4, 4]