Painting the Fence
On a pleasant day, Sovunya decided to repaint the fence surrounding her tree in the northwest. Over time, the fence has been painted and repainted multiple times, and now the paint has completely worn off, leaving it in need of a fresh coat.
The fence is made up of n numbered boards, each painted in one of k colors. Sovunya plans to choose a single color for all the boards once the painting is complete. Each day, she will paint a specific segment of the fence, defined by board numbers ranging from l to r, in the chosen color. Her goal is to select a color that allows her to finish painting the fence in the fewest possible days.
The task seems straightforward, but Sovunya must adhere to two rules while painting. First, she can paint no more than s boards in a single day, as she enjoys sports but cannot sustain physical labor for extended periods. Second, to conserve paint, a board that already has the desired color cannot be repainted in that color. Therefore, if any board within the segment l to r already has the chosen color, the entire segment cannot be painted in that color, and she must select a different segment.
Sovunya needs to determine the minimum number of days required to repaint the entire fence.
Input
The first line of the input contains three integers: n, k, and s (1 ≤ n, k, s ≤ 100000) - representing the number of boards in the fence, the number of different colors available, and the maximum number of boards that can be painted in one day, respectively.
The second line contains n integers c_i (1 ≤ c_i ≤ k), separated by spaces, indicating the current colors of the boards.
Output
Output a single integer - the minimum number of days Sovunya will need to repaint the fence.