Vasile organizeaza nunta prietenului sau Ion. Unul dintre elementele specifice zonei folclorice este un dans, denumit “trenul”. Toti invitatii se aseazaîn rând, unul dupa celalalt si fiecare persoana, cu exceptia primeia, pune mâinile pe umerii persoanei din fata sa. Apoi “trenul” astfel format se plimba prin întreaga încapere, în ritmul muzicii. Vasile are un simt estetic deosebit si vrea ca “trenul” sa arate bine. Daca doua persoane care stau una dupa alta au înaltimi foarte diferite, trenul nu arata bine. Familia lui Ion este teribil de conservatoare si nu ar permite ca în fata unui membru al familiei sa fie plasat un alt membru al familiei, mai tânar decât acesta. Sigur, ceilalti invitati pot sa stea cum doresc.

Cerinta

Date fiind înaltimile tuturor invitatilor si ordinea membrilor familiei lui Ion (descrescator dupa vârsta), scrieti un program care sa determine o modalitate de a construi “trenul” astfel încât nici unul dintre membrii familiei lui Ion sa nu aibaîn fata sa pe cineva din familie mai tânar, iar suma diferentelor de înaltime între oricare doi vecini sa fie minima.

Date de intrare

Pe prima linie a fisierului de intrare tren3.in se afla doua numere naturale N si K separate prin spatiu (N reprezinta numarul total de invitati, iar K numarul de membri ai familiei lui Ion).  Membrii familiei lui Ion sunt primii K invitati si sunt numerotati descrescator dupa vârsta. Deci, persoana 1 este cel mai batrân membru al familiei lui Ion, iar persoana K este cel mai tânar. Fiecare dintre urmatoarele N linii contine un numar natural V, care reprezinta, în ordine, înaltimile invitatilor (mai exact, pe linia i+1 se afla înaltimea invitatului i).

Date de iesire

Fisierul de iesire tren3.out contine pe prima linie valoarea minima a sumei diferentelor înaltimilor oricaror doi vecini. Fiecare din urmatoarele N linii contine câte un numar natural reprezentând numarul de ordine al invitatilor în ordinea în care acestia sunt plasati în “tren”.

Restrictii

• 1 <= N <= 10000
• 1 <= K <= 1000
• K <= N
• 1000 <= V <= 2200
• Solutia poate sa nu fie unica.

Exemple

prof. Serban Marinel
Liceul de Informatica "Gr. C. Moisil" Iasi