로미오가 줄리엣을 만나다
면접 대비시간 제한1초메모리 제한1024 MB
울타리 구간 중 Cowpulet이 C마리 이하인 가장 긴 연속 구간의 길이를 구합니다.
문제
농부 존은 서로 반목하는 소 떼 두 무리, 무툴 무리와 카우풀렛 무리를 기른다. 무툴 무리의 황소 중 하나인 로미오는 카우풀렛 무리의 암소 줄리엣과 사랑에 빠졌다. 로미오는 줄리엣을 만나고 싶지만, 다른 카우풀렛 소들에게 들키는 것은 원하지 않는다.
로미오와 줄리엣은 목장 울타리를 따라 가능한 한 넓은 구간에서 만나 풀을 뜯으려 한다. 다만 그 구간에 카우풀렛이 마리를 넘으면 안 된다. 그렇지 않으면 둘이 들킬 가능성이 너무 커지기 때문이다. 로미오는 마리의 카우풀렛 각각이 울타리의 어느 위치에서 풀을 뜯는지 기록해 두었다. 긴 일직선 울타리에는 번부터 번까지 번호가 붙은 개의 말뚝이 같은 간격으로 세워져 있다. 각 카우풀렛은 인접한 두 말뚝 사이에서 풀을 뜯는다. 로미오가 카우풀렛을 마리 이하로 포함하는, 울타리를 따라 이어진 가장 긴 구간의 길이를 구하도록 도와라.
입력
첫째 줄에 공백으로 구분된 정수 , , 가 주어진다. 제한은 , , 이다.
이어지는 개의 줄에는 각각 정수 가 하나씩 주어지며, 이다. 이는 카우풀렛 한 마리가 말뚝 와 말뚝 사이에서 풀을 뜯는다는 뜻이다. 같은 두 말뚝 사이에서 여러 마리가 풀을 뜯을 수도 있다.
출력
카우풀렛을 마리 이하로 포함하는 연속 구간 중 가장 큰 것의 크기(말뚝 사이 간격의 수)를 한 줄에 정수로 출력한다.
힌트
말뚝은 1, 2, 3, 4, 5, 6의 여섯 개다. 카우풀렛 두 마리 중 한 마리는 말뚝 2와 3 사이에서, 다른 한 마리는 말뚝 3과 4 사이에서 풀을 뜯는다.
말뚝 3부터 6까지의 구간(크기 3)에는 카우풀렛이 한 마리뿐이다.