만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

로미오가 줄리엣을 만나다

면접 대비

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

요약
울타리 구간 중 Cowpulet이 C마리 이하인 가장 긴 연속 구간의 길이를 구합니다.
난이도

쉬움10점 중 3점

유형
슬라이딩 윈도우, 배열
정답자
아직 제출이 없습니다

문제

농부 존은 서로 반목하는 소 떼 두 무리, 무툴 무리와 카우풀렛 무리를 기른다. 무툴 무리의 황소 중 하나인 로미오는 카우풀렛 무리의 암소 줄리엣과 사랑에 빠졌다. 로미오는 줄리엣을 만나고 싶지만, 다른 카우풀렛 소들에게 들키는 것은 원하지 않는다.

로미오와 줄리엣은 목장 울타리를 따라 가능한 한 넓은 구간에서 만나 풀을 뜯으려 한다. 다만 그 구간에 카우풀렛이 CC마리를 넘으면 안 된다. 그렇지 않으면 둘이 들킬 가능성이 너무 커지기 때문이다. 로미오는 NN마리의 카우풀렛 각각이 울타리의 어느 위치에서 풀을 뜯는지 기록해 두었다. 긴 일직선 울타리에는 11번부터 PP번까지 번호가 붙은 PP개의 말뚝이 같은 간격으로 세워져 있다. 각 카우풀렛은 인접한 두 말뚝 사이에서 풀을 뜯는다. 로미오가 카우풀렛을 CC마리 이하로 포함하는, 울타리를 따라 이어진 가장 긴 구간의 길이를 구하도록 도와라.

입력

첫째 줄에 공백으로 구분된 정수 NN, PP, CC가 주어진다. 제한은 1≤N≤10001 \le N \le 1000, 1≤P≤10001 \le P \le 1000, 0≤C≤10000 \le C \le 1000이다.

이어지는 NN개의 줄에는 각각 정수 XX가 하나씩 주어지며, 1≤X≤P−11 \le X \le P-1이다. 이는 카우풀렛 한 마리가 말뚝 XX와 말뚝 X+1X+1 사이에서 풀을 뜯는다는 뜻이다. 같은 두 말뚝 사이에서 여러 마리가 풀을 뜯을 수도 있다.

출력

카우풀렛을 CC마리 이하로 포함하는 연속 구간 중 가장 큰 것의 크기(말뚝 사이 간격의 수)를 한 줄에 정수로 출력한다.

힌트

말뚝은 1, 2, 3, 4, 5, 6의 여섯 개다. 카우풀렛 두 마리 중 한 마리는 말뚝 2와 3 사이에서, 다른 한 마리는 말뚝 3과 4 사이에서 풀을 뜯는다.

말뚝 3부터 6까지의 구간(크기 3)에는 카우풀렛이 한 마리뿐이다.

예제1

  1. 예제 1

    입력
    2 6 1
    2
    3
    
    예상 출력
    3