Voff

이미지 출처: 위키미디어

Atli는 이 아름다운 날에 일광욕을 하고 있다---이보다 더 좋을 수는 없을 것이다.

그러던 중 갑자기 Atli는 개가 짖는 소리를 듣고, 이어서 또 한 번, 그리고 계속해서 몇 번이고 듣는다. Atli는 개 짖는 소리가 성가시지만, 언제나 나쁜 상황에서도 좋은 점을 찾으려 하므로 이를 자신이 풀 수수께끼로 바꾸려고 한다.

먼저 Atli는 개가 짖는 소리를 들을 때마다 그때의 초를 하나의 정수 $a_i$로 나타내어 기록한다. 따라서 처음 짖은 시각은 $a_1$이고 마지막으로 짖은 시각은 $a_n$이다. Atli가 사는 현실에서 개는 짖는 사이에 숨을 쉬기 위해 적어도 $k$초가 필요하다.

이제 Atli는 짖고 있을 가능성이 있는 개의 최소 마릿수를 구하는 것을 자신의 수수께끼로 정한다. Atli는 이것이 꽤 좋은 수수께끼라고 생각한다. 이 수수께끼를 풀 수 있는가?

채점

그룹 | 점수 | 제한

1 | 15 | $1 \le n,a_i \le 100, k = 1$

2 | 35 | $1 \le n,k,a_i \le 100$

3 | 50 | 추가 제한 없음

입력은 두 줄로 주어진다. 첫 번째 줄에는 두 정수 $1 \le n,k \le 10^5$가 주어진다. 두 번째 줄에는 $n$개의 정수 $1 \le a_i \le 10^9$가 주어진다.

짖고 있을 가능성이 있는 개의 최소 마릿수를 나타내는 정수 하나를 출력한다.