Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

UPS12_C - Chińska kompania reprezentacyjna

Chińska kompania reprezentacyjna składa się z n żołnierzy. Podczas uroczystości zawsze stoją oni w jednym rzędzie i zawsze w tej samej kolejności. Zamiana miejscami dowolnej pary wojskowych spowodowałaby niepotrzebne zamieszanie.

Dowódcę kompanii strasznie denerwują różnice wzrostu pomiędzy żołnierzami. Postanowił on wyłączyć z udziału w uroczystościach od 0 do k wojskowych, tak aby uzyskać jak najdłuższy spójny podciąg żołnierzy o tym samym wzroście. Po wyłączeniu wojskowego z udziału w uroczystościach, żołnierze po jego prawej stronie przesuwają się jedną pozycję w lewo, aby zlikwidować przerwę.

Odpowiedz na pytanie. Jaka jest maksymalna długość spójnego podciągu wojskowych o tym samym wzroście jaki może uzyskać dowódca wyłączając z udziału w uroczystościach co najwyżej k żołnierzy?

Wejście

W pierwszej linii wejścia znajdują się dwie liczby całkowite n ∈ [1, 500000] i k ∈ [0, n - 1] oznaczające odpowiednio liczbę wojskowych w kompanii reprezentacyjnej oraz maksymalną liczbę żołnierzy jaką może wyłączyć z udziału w uroczystościach dowódca kompanii.

W drugiej linii wejścia znajduje się n liczb całkowitych z przedziału [1, 500000]. Liczba i-ta w kolejności określa wzrost wojskowego stojącego na i-tej pozycji.

Wyjście

Na wyjściu należy wypisać odpowiedź na pytanie, jaka jest maksymalna długość spójnego podciągu wojskowych o tym samym wzroście jaki może uzyskać dowódca wyłączając z udziału w uroczystościach co najwyżej k żołnierzy.

Przykład

Wejście:

10 2
185 180 185 185 180 190 185 185 190 195

Wyjście:

4

Wyjaśnienie do przykładu:

Optymalnym rozwiązaniem jest wyłączenie z udziału w uroczystościach wojskowego na pozycji 5, o wzroście 180, oraz wojskowego na pozycji 6, o wzroście 190. Wtedy obok siebie stanie 4 żołnierzy o wzroście 185.


Dodane przez:Maciej Boniecki
Data dodania:2019-03-24
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:12 Urodziny Polskiego Spoja

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.