Zoznam úloh

2. Bazalky a čili papričky

Kolo už skončilo. Môžeš si pozrieť vzorové riešenie.

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$.

Úloha

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í.

Formát vstupu

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í).

Príklad

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
Pre odovzdávanie sa musíš prihlásiť.
Trojsten

Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.

Kontakt
Ďalšie projekty