색깔 사각형

면접 대비

시간 제한1초메모리 제한512 MB

요약

색칠된 한 줄에서 최대 k개의 칸을 지워 같은 색이 연속된 최대 길이를 가장 크게 만들고, 그 최댓값을 출력한다.

난이도: 보통10점 중 6점
유형: 투 포인터, 슬라이딩 윈도우, 배열, 이분 탐색
정답자: 아직 제출이 없습니다

문제

그래픽 디자인은 Aditya의 새로운 열정이다. 그는 새 회사 Turmeric을 세웠고, 첫 고객이 새 로고를 디자인해 달라고 찾아왔다. 옛 로고는 한 줄로 늘어선 $n$ 개의 색깔 사각형으로 이루어져 있다. $i$ 번째 사각형은 $1 \leq s\_i \leq c$ 를 만족하는 수 $s\_i$ 로 표현되는 색으로 칠해져 있으며, $c$ 는 로고에 쓰인 전체 색의 수이다. 그런데 고객은 매우 까다로운 사람이다. 그는 Aditya가 사각형의 색을 바꾸는 것을 허락하지 않지만, 로고에서 최대 $k$ 개의 사각형을 지울 자유는 준다. Aditya는 로고의 미적 점수를 같은 색이 연속으로 이어진 사각형 개수의 최댓값이라고 생각한다. 새 로고의 미적 점수가 최대가 되도록 최대 $k$ 개의 사각형을 지우는 방법을 찾아라. Aditya는 사각형을 하나도 지우지 않아도 된다.

입력

입력의 첫 줄에는 공백으로 구분된 $3$ 개의 정수 $n$ , $c$ , $k$ 가 주어지며, $1 \leq n \leq 2 \cdot 10^5$ , $1 \leq c \leq 10^5$ , $1 \leq k < n$ 이다.

다음 줄에는 공백으로 구분된 $n$ 개의 정수 $s\_1, s\_2 \ldots, s\_n$ 이 주어지며, 각 사각형의 색을 나타낸다. $1 \leq s\_i \leq c$ 이다.

출력

새 로고의 미적 점수로 가능한 최댓값을 정수 하나로 출력한다.

예제2

예제 1
입력
```
3 1 2
1 1 1
```
예상 출력
```
3
```
예제 2
입력
```
10 3 2
1 2 1 1 3 2 1 1 2 2
```
예상 출력
```
4
```