29389번 - Покраска забора 다국어

문제

В один прекрасный день Совунья решила покрасить забор вокруг своего дерева на северо-западе. Когда-то давно его красили, потом краска облезала, потом его снова красили, потом краска снова облезала... В общем, к настоящему моменту забор совершенно потерял свой первоначальный вид.

Сейчас забор представляет собой $n$ пронумерованных досок, каждая имеет цвет от 1ドル$ до $k$. Для начала Совунья решила выбрать цвет, который будут иметь все доски после завершения покраски. После того, как она сделает это, она будет каждый день красить в этот цвет все доски на каком-то отрезке, то есть с номерами не меньше $l$ и не больше $r$. Совунья хочет так выбрать цвет, чтобы покрасить забор за наименьшее количество дней.

Казалось бы, что может быть проще? Однако, есть два правила, которые Совунья будет соблюдать при покраске. Первое правило заключается в том, что за день она может покрасить не больше $s$ досок (она, хоть и обожает спорт, уже не может очень много заниматься физическим трудом). Второе правило --- краску надо экономить, поэтому нельзя красить в какой-то цвет доску, которая уже имеет этот цвет. Соответственно, если на той части забора (всех досках с номерами от $l$ до $r$), которую Совунья собралась красить в какой-то цвет, есть хотя бы одна доска этого цвета, то весь отрезок красить в этот цвет нельзя, нужно выбирать другой.

Сейчас Совунья хочет знать, сколько дней у нее уйдет на покраску забора.

입력

В первой строке входного файла даны три числа: $n,ドル $k$ и $s$ (1ドル \le n, k, s \le 100{,円}000$) --- количество досок в заборе, количество различных возможных цветов и максимальная длина раскрашиваемого отрезка.

Вторая строка содержит $n$ целых чисел $c_i$ (1ドル \le c_i \le k$), разделённых пробелами --- цвета забора.

출력

Выведите одно целое число --- минимальное количество дней, за которое Совунья покрасит забор.

제한

힌트