34616번 - Hoven 서브태스크스페셜 저지다국어

문제

"U srcu Veldhovena pulsira neumorni ritam inovacija, potičući svakoga da se otisne na put otkrića i ostvari svoje najveće ambicije."

Grad Veldhoven možemo prikazati kao $n$ kuća poredanih u niz. Kuće označavamo brojevima od 1ドル$ do $n,ドル a udaljenost kuća $i$ i $j$ iznosi $|i − j|$.

Mr. Malnar, gradonačelnik Veldhovena, odlučio je ispred nekih kuća posaditi cvijeće. Za svaku kuću $i$ znamo cijenu $c_i$ sađenja cvijeća ispred te kuće u eurima. Razočaranost pojedine kuće definiramo kao njenu udaljenost do najbliže kuće ispred koje je posađeno cvijeće. Razočaranost cijelog grada definiramo kao maksimalnu razočaranost svih kuća.

Mr. Malnar raspolaže budžetom od $k$ eura. Budžet će biti takav da će on moći priuštiti sađenje cvijeća ispred barem jedne kuće. Mr. Malnar sada želi znati kolika je minimalna razočaranost grada koju može postići ako optimalno odabere kuće ispred kojih će posaditi cvijeće. Dodatno, zanima ga ispred kojih kuća treba posaditi cvijeće kako bi postigao minimalnu razočaranost.

입력

U prvom su retku brojevi $n$ i $k$ (1ドル ≤ n ≤ 10^6,ドル 1ドル ≤ k ≤ 10^9$), broj kuća u Veldhovenu i budžet kojim Mr. Malnar raspolaže.

U drugom se retku nalazi $n$ brojeva $c_1, c_2, \dots , c_n$ (1ドル ≤ c_i ≤ 10^9$), cijene sađenja cvijeća. Cvijeće će se uvijek moći posaditi ispred barem jedne kuće.

출력

U prvi redak ispišite minimalnu razočaranost grada.

U drugi redak ispišite broj odabranih kuća. Označimo taj broj s $q$.

U treći redak ispišite $q$ brojeva $b_1, b_2, \dots , b_q$ (1ドル ≤ b_i ≤ n$), indekse odabranih kuća. Indeksi moraju biti međusobno različiti. Poredak indeksa u izlazu nije bitan.

Ako postoji više različitih odabira kuća, ispišite bilo koje.

제한

서브태스크

노트

Pojašnjenje prvog probnog primjera: Ako Mr. Malnar posadi cvijeće ispred 3ドル$. i 7ドル$. kuće, potrošit će točno 3ドル$ eura. Razočaranosti kuća tada su redom 2ドル,ドル 1ドル,ドル 0ドル,ドル 1ドル,ドル 2ドル,ドル 1ドル,ドル 0ドル,ドル 1ドル,ドル 2ドル$ pa razočaranost grada iznosi 2ドル$.

Pojašnjenje drugog probnog primjera: Mr. Malnar može istu razočaranost postići i ako posadi cvijeće ispred 2ドル$. i 4ドル$. kuće.

Pojašnjenje trećeg probnog primjera: Još jedno valjano rješenje je posaditi cvijeće ispred 1ドル$. i 3ドル$. kuće. Tada je razočaranost 7ドル$. kuće jednako 4ドル$.