Contest problemset 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

Ostatnio na rynek czołgów został wypuszczony nowy model, który w ciągu minuty skacze o 2 lub 3 metry do przodu lub do tyłu. Generał rozważa jego zakup, ale najpierw potrzebuje dowiedzieć się ile minut zajmie mu przejechanie dokładnie N metrów do przodu. Pomóż mu, odpowiadając na Q takich zapytań.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita Q opisująca liczbę zapytań.

W każdym z następnych Q wierszy opisu zestawu danych znajduje się jedna liczba całkowita N oznaczająca liczbę metrów, o które pyta generał.

Wyjście

Wypisz dokładnie Q wierszy, gdzie i-ty z nich zawiera dokładnie jedną liczbę – minimalną liczbę minut potrzebnych na przejechanie N metrów nowym modelem czołgu.

Ograniczenia

1 ≤ Q ≤ 100 000, 1 ≤ N ≤ 10⁹.

Przykład

4
1
2
5
10

2
1
2
4

Podczas porannej zbiórki kierowcy czołgów typu 1 i 2 ustawiają się w linii. W przypadku, gdy dwaj kierowcy tego samego typu czołgów stoją obok siebie, zaczynają rozmawiać, jak to ich typ czołgu jest lepszy od tego drugiego. Bardzo przeszkadza to generałowi podczas odliczania, więc zastanawia się, ilu minimalnie kierowców musi wyprosić, żeby mógł przeprowadzić zbiórkę w spokoju. Znając ustawienie kierowców w linii, pomóż mu, odpowiadając na to pytanie.

Wejście

W pierwszym wierszu wejścia znajduje się liczba całkowita N określająca liczbę kierowców. W drugim wierszu wejścia znajduje się N liczb każda wynosząca 1 lub 2, określająca, który typ czołgu prowadzi kierowca i.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć minimalna liczba kierowców, których trzeba wyprosić.

Ograniczenia

1 ≤ N ≤ 1 000 000.

Przykład

6
1 1 2 2 2 1

3