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