Rakett

문제

Marslased ehitavad uut kosmoseraketti. See koosneb $NN$ moodulist, mis on liinil reas ja nummerdatud järjest $1\dots N1\; \backslash ldots\; N$. Moodulisse number $ii$ mahub $A_{i}A\_i$ liitrit kütust, kusjuures moodulite mahutavused on paarikaupa erinevad.

Nüüd tuleb moodulitest koostada $KK$ astet, millest igaüks koosneb ühest või mitmest järjestikusest moodulist nii, et iga moodul kuulub täpselt ühe astme koosseisu. Teisisõnu on vaja moodulite massiiv $AA$ jagada $KK$ mittetühjaks lõiguks.

Viimasel hetkel avastati, et rakett lendab kõige kiiremini, kui moodulid on igas astmes järjestatud mahtude kasvamise järjekorras. Moodulid on suured ja rasked ning seetõttu kulub kahe kõrvuti\-oleva mooduli omavahel vahetamiseks terve tund ja üksteisest kaugemaid mooduleid omavahel vahetada ei saagi.

Kirjutada programm, mis leiab minimaalse vahetuste arvu, mille järel on võimalik moodulid jagada $KK$ astmeks nii, et igas astmes on moodulid kasvavas järjekorras.

입력

Tekstifaili esimesel real on tühikuga eraldatud täisarvud $NN$ ja $KK$ ($1\le K\le N\le 20001\; \backslash le\; K\; \backslash le\; N\; \backslash le\; 2\backslash ,000$): vastavalt moodulite ja raketi astmete arv.

Faili teisel real on $NN$ tühikutega eraldatud täisarvu $A_{i}A\_i$ ($1\le A_i\le {10}^{9}1\; \backslash le\; A\_i\; \backslash le\; 10^9$): moodulite mahutavused nende numbrite järjekorras. Võib eedada, et arvud $A_{i}A\_i$ on paarikaupa erinevad.

출력

Tekstifaili väljastada üks täisarv: minimaalne moodulite ümberjärjestamiseks kuluv aeg.

10 3
9 30 45 2 5 7 10 3 16 22

0

7 3
7 6 5 4 3 2 1

5

5 2
1 4 2 5 3

1