配点 : $400$ 点

問題文

ラスク君は長さ $N$ の数列 $a$ を持っています。

数列の退屈さとは、連続する部分列であってすべて同じ要素からなるものの長さの最大値のことをいいます。

ラスク君は、数列 $a$ の要素を $K$ 個まで任意の整数に書き換えて、退屈さをできるだけ小さくしようとしています。

達成できる退屈さの最小値を求めてください。

制約

• 入力はすべて整数である。
• $1 \\leq K \\leq N \\leq 2\\times 10^5$
• $1 \\leq a_i \\leq N$

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$ $a_1$ $a_2$ $\\ldots$ $a_N$

出力

数列 $a$ の要素を $K$ 個以下書き換えたときの退屈さの最小値を出力せよ。

入力例 1

10 2
3 3 3 3 4 4 4 4 4 4

出力例 1

3

左から $1$ 番目の要素を $1$ に、$7$ 番目の要素を $2$ に書き換えると、数列は

$1, 3, 3, 3, 4, 4, 2, 4, 4, 4$

となり、退屈さは $3$ となります。

入力例 2

9 2
3 3 4 4 4 4 4 4 4

出力例 2

2

左から $4$ 番目の要素を $5$ に、$7$ 番目の要素を $1$ に書き換えると、数列は

$3, 3, 4, 5, 4, 4, 1, 4, 4$

となり、退屈さは $2$ となります。

入力例 3

5 5
3 1 4 1 5

出力例 3

1

全く書き換えを行わなくても構いません。