Broadcast

Orașul Satu Mare este reprezentat pe axa numerelor drept o înșiruire de $N$ case, fiecare casă $i$ aflându-se la coordonata $C_i$, pentru orice $i$ de la $1$ la $N$.

Recent, s-a aflat că urmează să aibă loc în oraș un eveniment de mare anvergură: Concursul Național de Informatică „Grigore Moisil”. Astfel, administrația vrea să anunțe în tot orașul că acest eveniment are loc, prin amplasarea strategică a unor turnuri de comunicare care să răspândească această veste.

Un turn de comunicare cu puterea $d$, plasat la poziția $p$ (care poate fi și o coordonată reală), poate transmite știrea către toate casele aflate la o distanță de cel mult $d$ de acesta. Formal, o casă situată la coordonata $x$ primește știrea dacă și numai dacă $|x - p| \le d$.

Deoarece amplasarea turnurilor este costisitoare, s-a decis alegerea unui singur cartier format din $M$ case adiacente (o secvență continuă de $M$ case din șirul inițial), unde vor fi amplasate turnurile. Astfel, știrea va ajunge direct la toți locuitorii din cartier, urmând ca aceștia să o răspândească mai departe.

Cerință

Municipalitatea vrea să achiziționeze $K$ turnuri, ale căror puteri $d_1, d_2, \dots, d_K$ urmează să fie stabilite. Atât configurarea puterilor pentru turnuri, cât și alegerea cartierului potrivit sunt decizii dificile. Din acest motiv, administrația dorește să calculeze întâi, pentru fiecare variantă posibilă de cartier (orice subsecvență de case continuă de lungime $M$), care este suma minimă necesară a puterilor ($d_1 + d_2 + \dots + d_K$), pentru ca cele $K$ turnuri să poată acoperi toate casele din acel cartier.

Date de intrare

Prima linie a fișierului de intrare conține trei numere întregi $N$, $M$ și $K$, separate prin câte un spațiu.

A doua linie conține $N$ numere întregi $C_1, C_2, \dots, C_N$, separate prin câte un spațiu, reprezentând coordonatele celor $N$ case.

Date de ieșire

Fișierul de ieșire va conține $N - M + 1$ numere, separate prin câte un spațiu. Al $i$-lea număr va reprezenta suma minimă a puterilor necesară pentru a acoperi cartierul format din casele cu indicii $i, i+1, \dots, i+M-1$. Fiecare valoare va fi afișată cu exact o singură zecimală (de exemplu, un număr întreg precum $5$ va fi afișat sub forma 5.0).

Restricții și precizări

• $1 \le N \le 200\ 000$
• $1 \le M \le N$
• $1 \le K \le M$
• $1 \le C_i \le 1\ 000\ 000\ 000$, pentru orice $1 \le i \le N$
• $C_1 \le C_2 \le \dots \le C_N$
• Atât puterea fiecărui turn, cât și coordonata unde este plasat pot fi numere reale (nu neapărat întregi, spre deosebire de coordonatele caselor, care se garantează că sunt numere întregi)

Exemplul 1

broadcast.in

5 3 2
2 4 8 12 16

broadcast.out

1.0 2.0 2.0

Explicație

Avem $N=5$ case, vrem să analizăm toate cartierele de $M=3$ case și avem $K=2$ turnuri la dispoziție.

Primul cartier este format din casele de la coordonatele $2, 4, 8$.
Pentru a le acoperi cu $2$ turnuri, putem plasa un turn la coordonata $3$ (acoperă casele de la $2$ și $4$ folosind o putere de $1$) și un turn la coordonata $8$ (acoperă casa de la $8$ folosind o putere de $0$). Suma puterilor utilizate este $1 + 0 = 1$. Deci pentru primul cartier răspunsul este $1$ (afișat 1.0).

Al doilea cartier este format din casele de la coordonatele $4, 8, 12$.
Putem plasa un turn la coordonata $6$ (acoperă $4$ și $8$ la distanța $2$) și unul la coordonata $12$ (acoperă casa $12$ la distanța $0$). Suma puterilor necesare este $2 + 0 = 2$ (afișat 2.0).

Al treilea cartier este format din casele de la coordonatele $8, 12, 16$.
Similar, putem plasa un turn la coordonata $10$ (acoperă $8$ și $12$ cu puterea $2$) și unul la $16$. Suma puterilor necesare este $2 + 0 = 2.0$.

Exemplul 2

broadcast.in

5 3 2
2 3 10 15 16

broadcast.out

0.5 2.5 0.5

Explicație

Avem tot $N=5$ case, $M=3$ și $K=2$.

Primul cartier este format din casele de la coordonatele $2, 3, 10$.
Cea mai bună strategie este să folosim primul turn pentru casele de coordonate $2$ și $3$, plasându-l exact la mijlocul lor, adică la coordonata $2.5$. Acesta va avea nevoie de o putere de $0.5$. Al doilea turn îl plasăm la coordonata $10$ cu puterea $0$. Suma puterilor utilizate este $0.5 + 0 = 0.5$, deci răspunsul este $0.5$.

Al doilea cartier este format din casele de la coordonatele $3, 10, 15$.
Putem plasa primul turn la coordonata $3$ (putere $0$) și al doilea turn la coordonata $12.5$ pentru a acoperi casele $10$ și $15$. Distanța de la $12.5$ la $10$, respectiv $15$, este $2.5$. Suma puterilor necesare este $0 + 2.5 = 2.5$.

Al treilea cartier este format din casele de la coordonatele $10, 15, 16$.
Similar cu primul caz, plasăm un turn la coordonata $10$ (putere $0$) și unul la coordonata $15.5$ pentru a acoperi casele $15$ și $16$ (putere $0.5$). Răspunsul este $0 + 0.5 = 0.5$.

În figura de mai jos se poate observa o ilustrare a plasării optime a turnurilor pentru cele trei cartiere din al doilea exemplu: