Chef found an array A of 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 ≤ L ≤ R ≤ N) is *bad* if \texttt{max}(A_{L}, A_{L+1}, \ldots , A_{R}) = \texttt{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.    

------ Input Format ------ 

- First line will contain T, 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},\ldots, A_{N} - the initial array.

------ Output Format ------ 

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

------ Constraints ------ 

$1 ≤ T ≤ 3\cdot 10^{4}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ K ≤ N$
$1 ≤ A_{i} ≤ 10^{9}$
- Sum of $N$ over all test cases does not exceed $3\cdot 10^{5}$.

----- Sample Input 1 ------ 
3
3 1
1 2 3
4 2
3 3 3 1
5 1
1 1 1 1 1

----- Sample Output 1 ------ 
3
4
7

----- explanation 1 ------ 
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]$.

Difficulty: HARD
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
import heapq

def comp(x, y):
	s = (x - y) % (y + 1)
	t = (x - y) // (y + 1)
	return s * (t + 1) + (y + 1) * t * (t + 1) // 2 + y

def hfindb(a, k):
	aa = [[comp(val, 1) - comp(val, 0), val, 0, idx, comp(val, 0), comp(val, 1)] for (idx, val) in enumerate(a)]
	heapq.heapify(aa)
	for i in range(k):
		x = heapq.heappop(aa)
		x[2] += 1
		x[4] = x[5]
		x[5] = comp(x[1], x[2] + 1)
		x[0] = x[5] - x[4]
		heapq.heappush(aa, x)
	return sum([x[4] for x in aa])
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	temp = a[0]
	tempc = 0
	count = []
	for val in a:
		if val == temp:
			tempc += 1
		else:
			count.append(tempc)
			tempc = 1
			temp = val
	count.append(tempc)
	count.sort(reverse=True)
	output = len(count)
	eff = sum([t // 2 for t in count])
	count = [val for val in count if val > 1]
	output -= len(count)
	if k >= eff:
		print(n)
	else:
		print(hfindb(count, k) + output)


from heapq import heappush, heappop

def fun(size, k):
	val = (size - k) // (k + 1)
	return k + (size - k) // (k + 1) * ((size - k) // (k + 1) + 1) // 2 * (k + 1 - (size - k) % (k + 1)) + (size - k) % (k + 1) * ((val + 1) * (val + 2) // 2)

def do(lis, k):
	myheap = []
	for i in lis:
		heappush(myheap, [-(i * (i + 1) // 2 - fun(i, 1)), [i, 1], i * (i + 1) // 2])
	ans = 0
	x = 0
	while x != k:
		val = heappop(myheap)
		if val[0] == 0:
			heappush(myheap, val)
		else:
			size = val[1][0]
			f = val[1][1]
			heappush(myheap, [-(fun(size, f) - fun(size, f + 1)), [size, f + 1], fun(size, f)])
		x += 1
	n = len(myheap)
	for i in range(n):
		ans += myheap[i][-1]
	return ans
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	arr = []
	prev = l[0]
	count = 1
	for i in range(1, n):
		if prev == l[i]:
			count += 1
		else:
			arr.append(count)
			prev = l[i]
			count = 1
	arr.append(count)
	print(do(arr, k))


def tri(n):
	return n * (n + 1) // 2

def cost(split):
	N = split[0]
	k = split[1]
	if N == 1:
		return 1
	if k >= N // 2:
		return N
	short = (N - k) // (k + 1)
	extra = short + 1
	n_extra = (N - k) % (k + 1)
	n_short = k + 1 - n_extra
	return n_short * tri(short) + n_extra * tri(extra) + k * 1
T = int(input())
for t in range(T):
	(N, K) = map(int, input().split())
	A = map(int, input().split())
	if K >= N // 2:
		print(N)
		continue
	previous = None
	partitions = []
	for a in A:
		if a == previous:
			partitions[-1] += 1
		else:
			partitions.append(1)
		previous = a
	if K >= sum([p // 2 for p in partitions]):
		print(N)
		continue
	splits = [[p, 0, cost([p, 0]) - cost([p, 1])] for p in partitions]
	if len(splits) == 1:
		print(cost([N, K]))
		continue
	splits.sort(key=lambda x: x[2])
	for k in range(K):
		this = splits.pop()
		this[1] += 1
		this[2] = cost([this[0], this[1]]) - cost([this[0], this[1] + 1])
		pos = None
		if this[2] <= splits[0][2]:
			pos = 0
		elif this[2] >= splits[-1][2]:
			pos = len(splits)
		else:
			lo = 0
			hi = len(splits) - 1
			while hi - lo > 1:
				med = (hi + lo) // 2
				if this[2] == splits[med][2]:
					pos = med
					break
				elif this[2] < splits[med][2]:
					hi = med
				else:
					assert this[2] > splits[med][2]
					lo = med
			if pos is None:
				pos = hi
		splits.insert(pos, this)
	result = 0
	for s in splits:
		result += cost(s)
	print(result)


from heapq import *

def get(le, k):
	y = le - k - 1
	g = y // (k + 2)
	j = y % (k + 2)
	u = k + 2 - j
	cost = u * (g * (g + 1) // 2) + j * ((g + 1) * (g + 2) // 2) + k + 1
	return cost
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	h = []
	i = 0
	while i < n:
		c = 0
		j = i
		while j < n and l[i] == l[j]:
			c += 1
			j += 1
		gain = c * (c + 1) // 2 - get(c, 0)
		heappush(h, [-gain, c, 0, c * (c + 1) // 2])
		i = j
	while k != 0 and h:
		x = heappop(h)
		if x[0] == 0:
			heappush(h, x)
			break
		else:
			gain = get(x[1], x[2]) - get(x[1], x[2] + 1)
			heappush(h, [-gain, x[1], x[2] + 1, get(x[1], x[2])])
		k -= 1
	ans = 0
	for i in h:
		x = abs(i[-1])
		ans += x
	print(ans)


from heapq import heappush, heappop
from itertools import groupby
T = int(input())
for _ in range(T):
	(N, K) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	h = []
	answer = 0
	for group in groupby(a):
		(value, it) = group
		m = sum((1 for elem in it))
		f = m * (m + 1) // 2
		answer += f
		for i in range(1, m // 2 + 1):
			k = (m - i) // (i + 1)
			r = (m - i) % (i + 1)
			new_f = r * (k + 1) * (k + 2) // 2 + (i + 1 - r) * k * (k + 1) // 2
			priority = new_f - f + 1
			heappush(h, priority)
			f = new_f
	for i in range(K):
		try:
			priority = heappop(h)
		except:
			break
		if priority == 0:
			break
		else:
			answer += priority
	print(answer)


from heapq import heapify, heappop, heappush

def tri(n):
	return n * (n + 1) // 2

def numbad(d, c):
	(x, r) = divmod(c - d, d + 1)
	return d + tri(x + 1) * r + tri(x) * (d + 1 - r)
for tcase in range(int(input())):
	(n, k) = [int(s) for s in input().split()]
	a = [int(s) for s in input().split()]
	(c, pq) = (1, [])
	for i in range(1, n):
		if a[i] != a[i - 1]:
			pq.append((numbad(1, c) - numbad(0, c), 0, c))
			c = 1
		else:
			c += 1
	pq.append((numbad(1, c) - numbad(0, c), 0, c))
	heapify(pq)
	(p, d, c) = heappop(pq)
	while k > 0 and c - d > d + 1:
		d += 1
		heappush(pq, (numbad(d + 1, c) - numbad(d, c), d, c))
		(p, d, c) = heappop(pq)
		k -= 1
	heappush(pq, (p, d, c))
	print(sum((numbad(d, c) for (p, d, c) in pq)))


import heapq

def cost(original, partitions):
	if partitions > (original + 1) // 2:
		return original
	ans = partitions - 1
	remaining = original - partitions + 1
	base = remaining // partitions
	leftover = remaining - base * partitions
	ans += leftover * ((base + 1) * (base + 2) // 2) + (partitions - leftover) * (base * (base + 1) // 2)
	return ans

def f(original, partitions):
	return cost(original, partitions) - cost(original, partitions + 1)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	(*a,) = map(int, input().split())
	a.append(a[-1] + 1)
	l = 0
	lengths = []
	prev = a[0]
	for i in a:
		if i == prev:
			l += 1
		else:
			heapq.heappush(lengths, (-f(l, 1), l, 1))
			l = 1
			prev = i
	for _ in range(k):
		if lengths[0][0] == 0:
			break
		(_, original, partitions) = heapq.heappop(lengths)
		partitions += 1
		heapq.heappush(lengths, (-f(original, partitions), original, partitions))
	print(sum((cost(original, partitions) for (_, original, partitions) in lengths)))