Kubo je veľký milovník štipľavých jedál. Na poličke v
kuchyni má $N$ koreničiek zoradených
od najmenej po najviac štipľavú. Každá korenička je označená číslom od
$1$ po $N$.
Raz však vyskúšal známu kalifornskú papričku a keď so slzami v očiach
odkladal koreničky naspäť, všetky ich poprehadzoval.
Keď sa neskôr spamätal a rozhodol sa ich znova upratať, zistil, že nemá dosť síl na veľké presuny. Dokáže vždy vymeniť len dve susedné koreničky – teda tie, ktoré stoja na pozíciách $A$ a $A + 1$.
Vašou úlohou je zistiť, na koľko najmenej susedných
výmen vie Kubo dosiahnuť,
aby sa K najmenej štipľavých koreničiek (čísel $1$ až $K$) nachádzalo na prvých $K$ pozíciách,
v ľubovoľnom poradí.
V prvom riadku vstupu sú dve celé čísla $N$ a $K$ – počet koreničiek a počet najmenej štipľavých koreničiek, ktoré chce Kubo dostať na začiatok.
V druhom riadku je $N$ rôznych celých čísel od $1$ po $N$, oddelených medzerami — aktuálne poradie koreničiek na poličke.
| Sada | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $1 \leq N \leq$ | $20$ | $10^3$ | $10^6$ | $10^6$ |
vo všetkých sadách platí $1 \leq K \leq N$ ## Formát výstupu
Vypíšte jedno celé číslo — minimálny počet susedných výmen, ktoré
musí Kubo vykonať,
aby sa najmenších $K$ koreničiek
presunulo na prvé $K$ pozície (v
ľubovoľnom poradí).
Input:
4 2
2 3 1 4
Output:
1
Stačí vymeniť 3-ku s 1-kou
Input:
7 1
1 6 5 7 4 2 3
Output:
0
V tomto vstupe už netreba nič vymieňať
Input:
5 3
4 1 5 3 2
Output:
5
Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.
Trojsten, o.z.
FMFI UK, Mlynská dolina
842 48 Bratislava
Programátorská súťaž pre základoškolákov
Materiály a úlohy na výučbu programovania
Intenzívny programátorský zážitok v lete