Фарбування огорожі#2634
В один приємний день Совунья вирішила перефарбувати паркан навколо свого дерева на північному заході. З часом паркан був пофарбований і перефарбований кілька разів, і тепер фарба повністю зносилася, тому йому потрібен свіжий шар.
Паркан складається з пронумерованих дощок, кожна з яких пофарбована в один із кольорів. Совунья планує вибрати один колір для всіх дощок після завершення фарбування. Кожного дня вона буде фарбувати певний відрізок паркану, визначений номерами дощок від до , у вибраний колір. Її мета — вибрати такий колір, щоб завершити фарбування паркану за найменшу кількість днів.
Завдання, здається, просте, але Совунья має дотримуватись двох правил під час фарбування. По-перше, за один день вона може фарбувати не більше ніж дощок, адже любить спорт, але не може довго займатися фізичною працею. По-друге, щоб зекономити фарбу, дошку, яка вже пофарбована у бажаний колір, не можна фарбувати повторно цим кольором. Тому якщо якась дошка в обраному відрізку від до вже має потрібний колір, весь цей сегмент не можна фарбувати у цей колір, і потрібно вибирати інший відрізок.
Совуньї потрібно визначити мінімальну кількість днів, необхідних для того, щоб перефарбувати весь паркан.
Перший рядок містить три цілих числа: , , (1 \leq n, k, s \leq 100000) — кількість дощок у паркані, кількість різних кольорів та максимальну кількість дощок, які можна пофарбувати за один день, відповідно.
Другий рядок містить цілих чисел c_i (1 \leq c_i \leq k), розділених пробілами, де зазначено поточний колір кожної дошки.
Виведіть єдине число — мінімальну кількість днів, необхідних Совуньї для фарбування паркану.
Приклад 1