Bubu's Bookshelf Chaos Minimization

Bubu's bookshelf is a complete mess! There are n books on the shelf with heights given by an array \(\displaystyle [a_1,a_2,\dots,a_n]\). The chaos value of the bookshelf is defined as the number of consecutive segments of books with the same height. For example, if the heights are \(\displaystyle [30,30,31,31,32]\) then the chaos value is 3; if the heights are \(\displaystyle [30,32,32,31]\) then the chaos value is also 3; however, \(\displaystyle [31,32,31,32,31]\) has a chaos value of 5.

Bubu wants to reduce the chaos as much as possible. However, feeling a bit tired, he decides that he will remove at most \(\displaystyle k\) books from the shelf and then reinsert these removed books at arbitrary positions on the shelf. The order of the books that are not removed must remain the same.

In other words, you are allowed to choose a set of indices (at most \(\displaystyle k\) books) to remove. The removed books can be reinserted anywhere and in any order, but the relative order of the remaining books is fixed. By doing so, you would like to achieve a final arrangement of books that minimizes the chaos value.

A key observation is that if we partition the bookshelf into several contiguous segments and then make each segment uniform (i.e. all books in that segment have the same height) by removing some books within that segment, the chaos value will be equal to the number of segments. For a segment covering indices \(\displaystyle l\) to \(\displaystyle r\), if you retain the most frequent height in that segment then you have to remove \[ \text{cost}(l,r)= (r-l+1)-\max_{x}\big(\text{frequency of } x \text{ in } [a_l,\dots,a_r]\big). \] Your task is to partition the array into a certain number of contiguous segments such that the sum of removal costs of all segments is at most \(\displaystyle k\), and the number of segments (i.e. the final chaos value) is minimized.

Input and Output:

You are given \(n\) and \(k\), and then an array of \(n\) integers representing the heights of the books. Output the minimum chaos value that can be achieved.

inputFormat

The first line contains two integers \(n\) and \(k\) separated by a space.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) representing the heights of the books.

outputFormat

Output a single integer — the minimum chaos value (i.e. the minimum number of contiguous uniform segments) achievable after at most \(k\) removals.

sample

5 1
30 30 31 31 32

2