Problem H
Voff
Þ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 |
