Стажировка ML — Вася и котики 2: максимум разных пород без обид соседей

Условие

У Васи дома n котиков, идущих в одну линию. У него одна переноска. Он хочет взять максимально возможное количество котиков разных пород. Но котики «обижаются», если их сосед той же породы остаётся, а нашего нет:

Котик обижается, если у него слева или справа котик той же породы и его не взяли, а соседа той же породы взяли (или левее/правее).

В формальной формулировке (из условия):

• Сначала Вася выбирает m котиков разных пород.
• Котик с индексом i обижается, если слева или справа (в исходном ряду) есть котик той же породы, не выбранный.
• Найти максимальное m, при котором никто не обижается.

Формат ввода

n k          # 1 ≤ n ≤ 10^6 + 1, 0 ≤ k ≤ n
b_1 ... b_n  # 0 ≤ b_i ≤ 10^6, порода

Формат вывода

Целое число m.

Пример 1

Ввод:
3 1
1 2 2

Вывод: 2

Пример 2

Ввод:
6 3
0 1 3 2 4 1

Вывод: 3

(Если взять породу 1 с индексом 1, то котик породы 1 с индексом 5 не обижается, потому что Вася не может взять второго котика породы 1 из-за соседа породы 4 между ними? Условие хитрое — см. примечание.)