Problem description

Jak dobrze wiadomo, żołnierze mogą należeć do batalionu czołgowego. Z niewiadomych jednak przyczyn żołnierze nie lubią się, jeżeli numery batalionów, do których należą różnią się o więcej niż d.

Generał w wolnym czasie lubi grać w brydża, ale zgodnie z zasadami potrzebuje do tego trzech dodatkowych graczy. Żeby zapewnić sobie trochę różnorodności, postanowił, że będzie grał każdego wieczoru z inną trójką żołnierzy: nie będzie dwóch dni, w których zagra z tą samą trójką.

Dodatkowo przez jego złe doświadczenia z przeszłości, wie, że jeżeli w wybranej trójce żołnierzy będzie jakaś para, która się nie lubi to gra będzie nieprzyjemna.

Zastanawia się więc przez ile dni może grać w brydża, tak aby każda gra była przyjemna oraz żeby nigdy nie zagrał z taką samą trójką żołnierzy. Wiedząc, do którego batalionu czołgów należy każdy z żołnierzy, odpowiedz na jego pytanie.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite N, d oznaczające odpowiednio liczbę żołnierzy oraz maksymalną różnicę w numerach batalionów czołgowych, do których należą żołnierze, którzy się lubią. W drugim wierszu wejścia znajduje się N liczb całkowitych a_i określających, do którego batalionu czołgów należy i-ty żołnierz.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się odpowiedź na pytanie generała.

Ograniczenia

1 ≤ a_i, d ≤ N ≤ 100 000.

Przykład

5 2
1 1 2 3 6

4