Maximizing Memory Fragments

You are given a canvas represented by n consecutive cells. Each cell has an initial color c_i (an integer in the range \([1,k]\)). In one operation, you can choose any cell and repaint it with any color from \([1,k]\). You are allowed to perform at most m operations.

A memory fragment is defined as a maximal contiguous block of cells with the same color. In other words, if two adjacent cells have different colors, they belong to different memory fragments. The score of the canvas is the total number of memory fragments that remain.

Your task is to determine the maximum number of memory fragments obtainable after at most \(m\) repainting operations. Note that even if you do not use all the operations, the answer is the maximum number of fragments you can achieve. Also, if \(k=1\) then no matter what operations you do, every cell will have the same color, so the answer is always 1.

Formally: You are given an array \(c_1, c_2, \dots, c_n\) where \(1 \le c_i \le k\). In each operation, you may change the color of any one cell to any integer in \([1,k]\). Let the number of memory fragments be the number of maximal contiguous segments of equal color. Compute the maximum possible number of fragments obtainable with at most \(m\) operations.

Note on Optimal Strategy: Transforming each contiguous block (of identical colors) into an alternating sequence increases the number of fragments. For a block of length \(L\), if left unchanged it counts as 1 fragment, and if fully alternated it can yield \(L\) fragments. However, the cost in operations depends on the block length. For instance, a block of length 2 can gain 1 extra fragment by one operation, while a block of length \(L \ge 3\) can gain 2 fragments with one operation (by repainting an interior cell to a color different from both neighbors) and each additional operation in that block adds at most 1 fragment. Overall, if you denote the number of blocks by \(B\), an operation allocation analysis shows that the final answer is given by:

[ \text{answer} = \min\Big(n,; B + \min\Big(2m,; \sum_{\text{block } i} (L_i - 1)\Big)\Big), ]

where \(L_i\) is the length of the \(i\)th contiguous block in the original array.

inputFormat

The first line contains three integers n, k, and m -- the length of the canvas, the number of colors, and the maximum number of repaint operations allowed, respectively.

The second line contains n integers c₁, c₂, …, c_n representing the initial colors of the canvas.

Constraints:

• 1 \(\leq n \leq 10^5\)
• 1 \(\leq k \leq 10^5\)
• 0 \(\leq m \leq 10^5\)
• 1 \(\leq c_i \leq k\)

outputFormat

Output a single integer, the maximum number of memory fragments (maximal contiguous segments of equal color) that can be obtained after performing at most m operations.

sample

5 3 1
1 1 1 1 1

3