culori

În jurul muzeului din orașul Smallville exista un gard ce conține $N$ scânduri de înălțimi diferite. Putem spune că scândura $i$ are înălțimea $H_i$. Directorul muzeului le-a cerut angajaților să vopsească acest gard cu un număr minim de culori, astfel încât să se respecte următoarea condiție: pentru un număr întreg $K$ cunoscut, orice secvență de $K$ scânduri consecutive nu trebuie să conțină $2$ scânduri de aceeași înălțime, colorate identic.

Cerință

Scrieţi un program care să găsească numărul minim de culori ce vor fi folosite pentru a colora gardului.

Date de intrare

Fişierul de intrare culori.in conţine:

• Pe prima linie, N K - două numere întregi reprezentând numărul de scânduri și lungimea secvenței.
• Pe următoarea linie, $N$ numere naturale $H_i$ reprezentand înălțimile celor $N$ scânduri.

Date de ieșire

Fişierul de ieşire culori.out va conţine un număr întreg $C$ reprezentând numărul minim de culori folosite.

Restricții și precizări

• $1 \leq K \leq 200 \ 000$;
• $1 \leq K \leq N \leq 1 \ 000 \ 000$;
• $1 \leq H_i \leq 1 \ 000$;
• Pentru 50% din punctaj, $1 \leq K \leq N \leq 5 \ 000$;
• Pentru 80% din punctaj, $1 \leq K \leq N \leq 200 \ 000$;

Exemplu

culori.in

6 4
1 1 2 1 3 2

culori.out

3

Explicație

O posibilă colorare a scândurilor folosind culorile 1, 2, 3 este: 1 2 1 3 1 2.
Există $3$ secvențe: 1 1 2 1, 1 2 1 3 si 2 1 3 2 și orice secvență respectă condiția din enunț.