WhiteRaptor наконец-то нашел своих сородичей в TheRaptorLand! В отличие от обычных WhiteRaptor, в TheRaptorLand обитает множество цветных ящеров: PinkRaptor, BlueRaptor и GreenRaptor.
WhiteRaptor выстроил всех $n$ ящеров в TheRaptorLand в ряд, пронумеровав их от $1$ до $n$ слева направо. $i$-й ящер слева имеет цвет $c[i]$. Он хочет выбрать несколько ящеров, чтобы они навсегда составили ему компанию в его подвале. Однако он может сделать это, только удалив ноль или более ящеров с левого и правого концов ряда и оставив всех остальных ящеров.
Чтобы никто из оставшихся ящеров не чувствовал себя обделенным, он хочет, чтобы разность между частотой самого часто встречающегося цвета и частотой самого редко встречающегося цвета не превышала $k$. Заметьте, что если ящеры какого-то цвета не остались, частота самого редкого цвета считается равной $0$.
Помогите WhiteRaptor найти максимальное количество ящеров, которое он может оставить!
Входные данные
Ваша программа должна считывать данные из стандартного потока ввода. Первая строка содержит два целых числа $n$ и $k$. Вторая строка содержит $n$ целых чисел $c[1], c[2], \dots, c[n]$, разделенных пробелами.
Выходные данные
Ваша программа должна выводить данные в стандартный поток вывода. Выведите одно целое число — максимальное количество ящеров, которое он может оставить.
Ограничения
Для всех тестовых случаев входные данные удовлетворяют следующим условиям:
- $1 \le n \le 200\,000$
- $0 \le k \le 200\,000$
- $1 \le c[i] \le 3$ для всех $1 \le i \le n$
Ваша программа будет протестирована на входных данных, удовлетворяющих следующим ограничениям:
| Подзадача | Баллы | Дополнительные ограничения |
|---|---|---|
| 0 | 0 | Примеры тестов |
| 1 | 5 | $n \le 500$ |
| 2 | 9 | $n \le 2000$ |
| 3 | 11 | $c[i] \le 2$ |
| 4 | 15 | $k = 0$ |
| 5 | 16 | Существует $1 \le j \le n$ такое, что $c[i] \neq 3$ для всех $i \le j$ и $c[i] = 3$ для всех $i > j$ |
| 6 | 20 | В любой непрерывной последовательности из 3 или более ящеров цвет 3 является наименее частым |
| 7 | 24 | Нет дополнительных ограничений |
Примеры
Входные данные 1
11 2 2 2 1 2 1 3 2 1 2 1 1
Выходные данные 1
7
Примечание 1
От 3-го до 9-го ящера количество ящеров с $c[i] = 1, 2$ и $3$ равно $3, 3$ и $1$ соответственно. Поскольку разность между максимальной и минимальной частотами не превышает $k = 2$, этот набор ящеров удовлетворяет критерию WhiteRaptor.
Примером недопустимого набора ящеров является отрезок с 3-го по 10-го ящера, так как добавление еще одного ящера с $c[i] = 1$ приводит к тому, что частота самого частого цвета становится равной $4$. Результирующая разность между максимальной и минимальной частотами равна $3$, что превышает $k = 2$.
Можно показать, что $7$ — это наибольшее количество ящеров, которое WhiteRaptor может оставить, чтобы при этом соблюдался его критерий.
Входные данные 2
6 2 2 1 3 3 3 3
Выходные данные 2
5
Примечание 2
WhiteRaptor должен выбрать ящеров с 1-го по 5-й.
Входные данные 3
7 0 1 2 1 2 1 2 1
Выходные данные 3
0
Примечание 3
Поскольку любая непрерывная последовательность ящеров не будет содержать ящера с $c[i] = 3$, частота самого редкого цвета всегда будет равна $0$. Это означает, что WhiteRaptor не может выбрать ни одной непустой последовательности ящеров. Следовательно, ответ — $0$.
Заметьте, что этот тест удовлетворяет подзадаче 5, так как мы можем принять $j = n$ (ящеры цвета 3 не появятся).