Mistrzostwa Polski Szkół Średnich w Programowaniu Zespołowym 2024

2020-2022 2023 Regulations Schedule RODO info

Problem description


Brydż
(brydz)
Limit pamięci: 256 MB
Limit czasu: 2.00 s

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 ai 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 ≤ ai, d ≤ N ≤ 100 000.

Przykład

Wejście Wyjście Wyjaśnienie
5 2
1 1 2 3 6
4

Generał może grać zagrać z trójkami {1, 2, 3}, {1, 2, 4}, {1, 3, 4} oraz {2, 3, 4}.