WhiteRaptor가 드디어 TheRaptorLand에서 자신의 동족을 찾았습니다! 평범한 WhiteRaptor와 달리, TheRaptorLand에는 PinkRaptor, BlueRaptor, GreenRaptor와 같이 색깔이 있는 랩터들이 다양하게 존재합니다.
WhiteRaptor는 TheRaptorLand에 있는 모든 $n$마리의 랩터를 왼쪽에서 오른쪽으로 $1$부터 $n$까지 번호를 매겨 일렬로 세웠습니다. 왼쪽에서 $i$번째 랩터의 색깔은 $c[i]$입니다. 그는 자신의 지하실에서 영원히 함께할 랩터들을 선택하려고 합니다. 하지만 그는 오직 줄의 왼쪽 끝과 오른쪽 끝에서 0마리 이상의 랩터를 제거하고, 남아있는 모든 랩터를 유지하는 방식으로만 랩터를 선택할 수 있습니다.
남아있는 랩터들 중 어느 누구도 소외되지 않도록 하기 위해, 그는 가장 많이 나타나는 랩터 색깔의 빈도와 가장 적게 나타나는 랩터 색깔의 빈도 차이가 $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 i \le n$에 대하여 $1 \le c[i] \le 3$
프로그램은 다음 제한을 만족하는 입력 인스턴스에서 테스트됩니다:
| 서브태스크 | 점수 | 추가 제한 |
|---|---|---|
| 0 | 0 | 예제 테스트 케이스 |
| 1 | 5 | $n \le 500$ |
| 2 | 9 | $n \le 2000$ |
| 3 | 11 | $c[i] \le 2$ |
| 4 | 15 | $k = 0$ |
| 5 | 16 | 모든 $i \le j$에 대해 $c[i] \neq 3$이고, 모든 $i > j$에 대해 $c[i] = 3$인 $1 \le j \le n$이 존재함 |
| 6 | 20 | 3마리 이상의 연속된 랩터 시퀀스에서 색깔 3이 가장 적게 나타남 |
| 7 | 24 | 추가 제한 없음 |
예제
입력 1
11 2 2 2 1 2 1 3 2 1 2 1 1
출력 1
7
참고
랩터 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
참고
WhiteRaptor는 랩터 1부터 랩터 5까지를 선택해야 합니다.
입력 3
7 0 1 2 1 2 1 2 1
출력 3
0
참고
연속된 랩터 시퀀스에 $c[i] = 3$인 랩터가 포함되지 않으면, 가장 적게 나타나는 색깔의 빈도는 항상 0이 됩니다. 이는 WhiteRaptor가 비어있지 않은 랩터 시퀀스를 선택할 수 없음을 의미합니다. 따라서 출력은 0입니다.
이 테스트 케이스는 $j = n$으로 설정할 수 있으므로(색깔 3인 랩터가 나타나지 않음) 서브태스크 5를 만족합니다.