WhiteRaptor w końcu odnalazł swoich pobratymców w TheRaptorLand! W przeciwieństwie do zwykłego WhiteRaptora, TheRaptorLand zamieszkuje różnorodna grupa kolorowych raptorów: PinkRaptor, BlueRaptor oraz GreenRaptor.
WhiteRaptor ustawił wszystkie $n$ raptorów w TheRaptorLand w szeregu, numerując je od $1$ do $n$ od lewej do prawej strony. $i$-ty raptor od lewej ma kolor $c[i]$. Chce on wybrać pewną grupę raptorów, aby na zawsze dotrzymywały mu towarzystwa w jego piwnicy. Może to jednak zrobić jedynie poprzez usunięcie zera lub większej liczby raptorów z lewego i prawego końca szeregu, zachowując wszystkie pozostałe raptory.
Aby upewnić się, że żaden z pozostałych raptorów nie będzie wykluczony, chce, aby różnica między częstością występowania najczęstszego koloru raptora a częstością występowania najrzadszego koloru raptora nie przekraczała $k$. Zauważ, że jeśli w wybranej grupie nie pozostał żaden raptor określonego koloru, częstość występowania najrzadszego koloru wynosi $0$.
Pomóż WhiteRaptorowi znaleźć maksymalną liczbę raptorów, które może zatrzymać!
Wejście
Twój program musi czytać dane ze standardowego wejścia. Pierwsza linia wejścia zawiera dwie liczby całkowite $n$ oraz $k$. Druga linia wejścia zawiera $n$ liczb całkowitych oddzielonych spacjami $c[1], c[2], \dots, c[n]$.
Wyjście
Twój program musi wypisać wynik na standardowe wyjście. Wypisz jedną liczbę całkowitą, maksymalną liczbę raptorów, które może zatrzymać.
Podzadania
Dla wszystkich przypadków testowych dane wejściowe spełniają następujące warunki: $1 \le n \le 200\,000$ $0 \le k \le 200\,000$ * $1 \le c[i] \le 3$ dla wszystkich $1 \le i \le n$
Twój program będzie testowany na instancjach spełniających poniższe ograniczenia:
| Podzadanie | Wynik | Dodatkowe ograniczenia |
|---|---|---|
| 0 | 0 | Przykładowe przypadki testowe |
| 1 | 5 | $n \le 500$ |
| 2 | 9 | $n \le 2000$ |
| 3 | 11 | $c[i] \le 2$ |
| 4 | 15 | $k = 0$ |
| 5 | 16 | Istnieje takie $1 \le j \le n$, że $c[i] \neq 3$ dla wszystkich $i \le j$ oraz $c[i] = 3$ dla wszystkich $i > j$ |
| 6 | 20 | W każdym spójnym ciągu 3 lub więcej raptorów, kolor 3 jest najrzadszy |
| 7 | 24 | Brak dodatkowych ograniczeń |
Przykład
Wejście 1
11 2 2 2 1 2 1 3 2 1 2 1 1
Wyjście 1
7
Uwagi
Od raptora 3 do raptora 9, liczby raptorów o kolorach $c[i] = 1, 2, 3$ wynoszą odpowiednio 3, 3 i 1. Ponieważ różnica między maksymalną a minimalną częstością nie przekracza $k = 2$, ten zestaw raptorów spełnia kryterium WhiteRaptora.
Przykładem nieprawidłowego zestawu raptorów jest zakres od raptora 3 do raptora 10, ponieważ dodanie kolejnego raptora z $c[i] = 1$ powoduje, że częstość występowania najczęstszego koloru wynosi 4. Wynikowa różnica między maksymalną a minimalną częstością wynosi 3, co przekracza $k = 2$.
Można wykazać, że 7 to największa liczba raptorów, które WhiteRaptor może zatrzymać, spełniając swoje kryterium.
Wejście 2
6 2 2 1 3 3 3 3
Wyjście 2
5
Uwagi
WhiteRaptor powinien wybrać raptory od 1 do 5.
Wejście 3
7 0 1 2 1 2 1 2 1
Wyjście 3
0
Uwagi
Ponieważ żaden spójny ciąg raptorów nie zawiera raptora z $c[i] = 3$, częstość występowania najrzadszego koloru zawsze będzie wynosić 0. Oznacza to, że WhiteRaptor nie może wybrać żadnego niepustego ciągu raptorów. W związku z tym wynikiem jest 0.
Zauważ, że ten przypadek testowy spełnia warunki podzadania 5, ponieważ możemy przyjąć $j = n$ (nie pojawią się żadne raptory o kolorze 3).