Achievements
면접 대비시간 제한1초메모리 제한512 MB
스웨덴어를 연습한 날과 유료 결제로 채울 수 있는 날 수가 주어질 때, 건너뛴 날 수가 날 수 이하인 연속 날짜 구간의 최대 길이를 구합니다.
문제
그렉이 매일 스웨덴어를 연습한다는 사실을 알고 있었는가? 거의 매일이다.
그렉이 언어를 배울 때 쓰는 앱은 사용자의 흥미를 유지하려고 성취 배지를 준다. 성취 중 하나는 최장 연속 기록, 즉 그렉이 스웨덴어를 연습한 연속 일수의 최댓값에 대한 것이다. 그렉이 매일 연습하지는 않으므로 빈 날이 생긴다는 점을 기억하자. 다행히 앱에서는 연습하지 않은 날의 값을 지불하고도 성취를 얻을 수 있다.
그렉이 실제로 스웨덴어를 연습한 날들과 그가 값을 지불할 의향이 있는 날의 수가 주어졌을 때, 그가 달성할 수 있는 최장 연속 기록은 얼마인가?
입력
입력은 다음과 같다.
- 두 정수 n과 p가 주어지는 한 줄 (1 ≤ n, p ≤ 2 · 10^5). n은 그렉이 앱으로 연습한 날의 수이고, p는 그가 값을 지불할 의향이 있는 날의 수이다.
- n개의 서로 다른 정수 d1, . . . , dn이 주어지는 한 줄 (0 ≤ d1 < d2 < . . . < dn ≤ 10^6). 이는 그렉이 실제로 연습한 날들이다.
출력
지불한 날을 최적으로 사용했을 때 그렉이 달성할 수 있는 최장 연속 기록의 길이를 출력한다.