soldiers

$N$ soldați se așează în linie, de la stânga la dreapta. Fiecare soldat are un număr distinct de la $1$ la $N$ asociat. În fiecare dimineață sergentul responsabil vine și cheamă în față pe soldații corespunzători numerelor $1 \ 2 \dots K$. Dacă aceștia nu se află chiar în ordinea $1 \ 2 \dots K$ pe toți cei $N$ soldați îi va aștepta o pedeapsă cruntă.

Sergentul, observând că cei $K$ soldați nu sunt așezați corect, va începe să ordoneze soldații. El îi va ordona pe cei $K$ soldați folosind interschimbări de soldați adiacenți. La fiecare pas va alege $2$ soldați aflați în ordine consecutivă (din cei $N$) și îi va obliga să își interschimbe pozițiile.

Sergentul este foarte eficient și îi va ordona pe soldații cu numerele $1 \ 2 \dots K$ folosind un număr minim de interschimbări, însă pentru fiecare astfel de interschimbare îi va obliga pe toți soldații să execute o flotare.

Astăzi sergentul este prea nervos și ocupat, și drept urmare vă roagă pe voi să îi spuneți câte flotări trebuie să execute cei $N$ soldați.

Detalii de implementare

Trebuie să implementați următoarea funcție:

long long minimum_swaps(std::vector<int> S, int K);

Funcția minimum_swaps va fi apelată exact o dată pentru fiecare test. $S$ va conține ordinea celor $N$ soldați de la stânga la dreapta, iar $K$ va reprezenta numărul de soldați chemați în față. Se garantează că vectorul $S$ va conține exact o dată fiecare număr de la $1$ la $N$ și că $1 \leq K \leq N$.

Funcția trebuie să returneze un număr natural, reprezentănd câte flotări vor fi obligați să execute cei $N$ soldați pentru că nu au fost ordonați corespunzător.

Punctare

Model de grader

Atenție! Acest grader nu este neapărat cel folosit pentru evaluarea submisiilor.

Vi se pune la dispoziție un grader pentru a vă putea compila și testa codul local. Acesta va citi de la consolă datele de intrare în următorul format:

• linia $1$: $N \ K$, reprezentând numărul de soldați, respectiv numărul de soldați chemați în față.
• linia $2$: $S_0 \ S_1 \dots S_{N-1}$ (separate prin câte un spațiu)
  Graderul va afișa în consolă răspunsul vostru, pe o singură linie, ca pe un număr întreg în baza $10$.

Exemplul 1

stdin

6 3
6 1 5 2 4 3

stdout

0

Explicație

În primul exemplu, sergentul îi cheamă pe cei cu numerele $1$, $2$ și $3$. Din fericire aceștia se află deja în ordinea corectă așa că soldații nu sunt obligați să execute flotări.

Exemplul 2

stdin

6 5
6 1 5 2 4 3

stdout

4

Explicație

În al doilea exemplu, din cauza soldaților cu numerele $4$ și $5$ ordinea soldaților nu mai este corectă.
Sergentul îi poate aranja în felul următor folosind 4 interschimbări: $6 \ 1 \ (5 \ 2) \ 4 \ 3 \rightarrow \ 6 \ 1 \ 2 \ 5 \ (4 \ 3) \rightarrow 6 \ 1 \ 2 \ (5 \ 3) \ 4 \rightarrow 6 \ 1 \ 2 \ 3 \ (5 \ 4) \rightarrow 6 \ 1 \ 2 \ 3 \ 4 \ 5$.
Nu există nicio metodă de a aranja soldații cu numerele $1 \ 2 \ 3 \ 4$ și $5$ folosind mai puțin de $4$ interschimbări.

Exemplul 3

stdin

7 4
4 5 1 7 2 6 3

stdout

6

Explicație

În cel de-al treilea exemplu, una din metodele de a ordona soldații cu numerele $1 \ 2 \ 3$ și $4$ folosind $6$ interschimbări este:

$(4 \ 5) 1 \ 7 \ 2 \ 6 \ 3 \rightarrow 5 \ 4 \ 1 \ 7 \ 2\ (6\ 3) \rightarrow 5 \ (4 \ 1) \ 7 \ 2 \ 3 \ 6 \rightarrow 5 \ 1 \ (4 \ 7) \ 2 \ 3 \ 6 \rightarrow 5 \ 1 \ 7 \ (4 \ 2) 3 \ 6 \rightarrow 5 \ 1 \ 7 \ 2 \ (4 \ 3) 6 \rightarrow 5 \ 1 \ 7 \ 2 \ 3 \ 4 \ 6$.