28305번 - 세미나 배정

문제

DEVOCEAN은 SK그룹의 대표 개발자 커뮤니티이자, 내/외부 개발자 간 소통과 성장을 위한 플랫폼이다. DEVOCEAN의 콘텐츠로는 SK 개발자들이 직접 작성한 최신 개발 관련 글과 기술을 공유하고, 테크뉴스 등을 소개하는 ‘블로그’, 최신 트렌드 동영상과 SK Tech Summit, 세미나 등으로 구성된 ‘동영상’, SK가 공개한 오픈 소스 포털로 안내하는 ‘오픈소스’ 등이 있다.

DEVOCEAN에서 세미나 $N$개를 주최하려고 한다. DEVOCEAN의 행사 기획 담당자 성호는 다음 조건을 지켜 각 세미나의 일정을 정해야 한다.

• 각 세미나는 연속된 $T$일 동안 진행되어야 한다. 구체적으로, $i$번째 세미나는 $m_{i}$일차부터 $m_{i}+T-1$일차까지 매일 진행되어야 한다. 성호는 $m_{i}$를 정해야 한다. $m_{i}$는 반드시 양의 정수여야 한다.
• 각 세미나의 $T$일 중 하루에는 외부전문가의 특강이 진행되어야 한다. $i$번째 세미나의 외부전문가가 참석할 수 있는 날이 $a_{i}$일차밖에 없기 때문에, $a_{i}$일차는 $i$번째 세미나가 진행되는 $T$일 중 하루여야 한다. 즉, $m_{i}\leq a_{i}\leq m_{i}+T-1$이어야 한다.

성호는 세미나에 사용할 세미나실을 미리 대여하기로 하였다. 하나의 세미나실에서는 같은 날에 최대 하나의 세미나를 진행할 수 있지만, 다른 날에 서로 다른 세미나를 진행하는 것은 가능하다. 한 번이라도 사용할 세미나실은 모두 빌려야 하기 때문에, 성호는 진행되는 세미나가 가장 많은 날의 세미나 수를 최소화하고 싶다. 성호를 도와 이 값을 구해주자!

입력

첫 번째 줄에 $N,ドル $T$가 공백으로 구분되어 입력된다. (1ドル\leq N\leq 200,円 000$; 1ドル\leq T\leq 10^{9}$)

두 번째 줄에 $a_{1},,円 a_{2},,円\cdots ,,円 a_{N}$이 공백으로 구분되어 입력된다. (1ドル\leq a_{i}\leq 10^{9}$)

출력

진행되는 세미나가 가장 많은 날의 세미나 수의 최솟값을 출력한다.

제한

노트

첫 번째 예제에서, 다섯 개의 세미나를 다음과 같은 일정으로 진행한다.

• 첫 번째 세미나를 3ドル$일차부터 5ドル$일차까지 진행한다.
• 두 번째 세미나를 6ドル$일차부터 8ドル$일차까지 진행한다.
• 세 번째 세미나를 1ドル$일차부터 3ドル$일차까지 진행한다.
• 네 번째 세미나를 4ドル$일차부터 6ドル$일차까지 진행한다.
• 다섯 번째 세미나를 7ドル$일차부터 9ドル$일차까지 진행한다.

이 경우, 1ドル$일차부터 9ドル$일차까지 각 날에 진행되는 세미나의 수는 차례로 1,ドル,円 1,,円 2,,円 2,,円 2,,円 2,,円 2,,円 2,,円 1$개이다. 따라서 진행되는 세미나가 가장 많은 날의 세미나 수는 2ドル$개이다.

2ドル$개 이상의 세미나가 진행되는 날이 없게 일정을 정하는 방법은 없음을 증명할 수 있다.