Start

2019-03-23 11:00 CET

Beta 2019

End

2019-03-23 17:00 CET
The end is near!
Contest is over.
Not yet started.
Contest is starting in -266 days 9:23:52

Time elapsed

6:00:00

Time remaining

0:00:00

Problem H
Voff

/problems/iceland.voff/file/statement/is/img-0001.jpg
Mynd fengin af wikimedia.org
Atli er í sólbaði á þessum yndislega degi—það gæti ekkert verið betra.

Þangað til allt í einu heyrir Atli gelt, og svo annað, og svo aftur og aftur og aftur. Atla finnst geltin pirrandi en hann reynir alltaf að gera gott úr slæmu þannig hann reynir að breyta þessu í gátu fyrir sig til að leysa.

Fyrst skrifar Atli niður sekúnduna í hvert skipti sem hann heyrir gelt táknað með einni heiltölu $a_ i$. Tímasetning fyrsta geltsins er því $a_1$ og tímasetning síðasta geltsins er $a_ n$. Í veruleikanum hans Atla þá þurfa hundar í minnsta lagi $k$ sekúndur til að anda milli gelta.

Nú ákveður Atli að gátan sín sé hver er minnsti fjöldi hunda sem gæti verið að gelta. Atli hugsar að þetta sé frekar góð gáta. Getur þú leyst hana?

Inntak

Inntakið er tvær línur. Fyrri línan inniheldur tvær heiltölur $1 \le n,k \le 10^5$. Seinni línan inniheldur $n$ heiltölur $1 \le a_ i \le 10^9$.

Úttak

Skrifaðu út eina heiltölu, minnsta fjölda hunda sem gæti verið að gelta.

Stigagjöf

Hópur

Stig

Takmarkanir

1

15

$1 \le n,a_ i \le 100, k = 1 $

2

35

$1 \le n,k,a_ i \le 100 $

3

50

Engar frekari takmarkanir

Sample Input 1 Sample Output 1
3 1
1 2 3
1
Sample Input 2 Sample Output 2
3 2
1 2 3
2
Sample Input 3 Sample Output 3
3 3
1 2 3
3
Sample Input 4 Sample Output 4
3 4
1 2 3
3