== include(page="template/taskheader" task_id="stalpisori") ==

Alexandra este studenta la facultatea de informatica. Astazi, mergand inapoi spre casa a observat ca pe strada pe care merge se afla $N$ stalpisori amplasati pe marginea trotuarului. Fiind studenta la informatica, ea se gandeste imedia la o problema de informatica plecand de la acest lucru. Ea se intreaba care este distanta minima $D$, astfel incat pentru fiecare din cei $N$ stalpisori, in intervalul $[P{~i~} - D, P{~i~} + D]$ sa se afle cel putin $K$ stalpisori, $P{~i~}$ reprezentand distanta de la inceputul strazii pana la stalpisorul $i$. Avand in vedere ca Alexandra a picat examenul de algoritmica, ea va roaga pe voi sa o ajutati sa rezolve aceasta problema.

Alexandra este studenta la facultatea de informatica. Astazi, mergand inapoi spre casa a observat ca pe strada pe care merge se afla $N$ stalpisori amplasati pe marginea trotuarului. Fiind studenta la informatica, ea se gandeste imediat la o problema de informatica plecand de la acest lucru. Ea se intreaba care este distanta minima $D$, astfel incat pentru fiecare din cei $N$ stalpisori, in intervalul $[P{~i~} - D, P{~i~} + D]$ sa se afle cel putin $K$ stalpisori, $P{~i~}$ reprezentand distanta de la inceputul strazii pana la stalpisorul $i$. Avand in vedere ca Alexandra a picat examenul de algoritmica, ea va roaga pe voi sa o ajutati sa rezolve aceasta problema.

h2. Date de intrare

* $1 ≤ N ≤ 1.000.000$
* $1 ≤ K ≤ N$

* Pozitiile stalpisorilor sunt numere naturale distincte mai mici decat 2^32^

* Pozitiile stalpisorilor sunt numere naturale distincte strict mai mici decat 2^31^

* Pozitiile stalpisorilor vor fi date in *ordine crescatoare*
h2. Exemplu

| 9
|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="stalpisori") ==

4849