== include(page="template/taskheader" task_id="soldiers") ==

N soldati se aseaza in linie, de la stanga la dreapta. Fiecare soldat are un numar distinct de la 1 la n asociat. In fiecare dimineata sergenrul responsabil vine si cheama in fata pe soldatii corespunzatori numerelor 1 2 ... K
 
Daca acestia nu se afla chiar in ordinea 1 2 ... K pe toti cei N soldati ii va astepta o pedeapsa crunta. Sergentul, observand ca cei K soldati nu sunt asezati corect, va incepe sa ordoneze soldatii. El ii va ordona pe cei K soldati folosind interschimbari adiacente. La fiecare pas va alege 2 soldati aflati in ordine consecutiva (din cei n) si ii va obliga sa isi interschimbe pozitiile.
 
Sergentul este foarte eficient si ii va ordona pe soldatii cu numerele 1 2 ... K folosind un numar minim de interschimbari, insa pentru fiecare astfel de interschimbare ii va obliga pe toti soldatii sa execute o flotare.
 
Astazi sergentul este prea nervos si ocupat, si drept urmare va roaga pe voi sa ii spuneti cate flotari trebuie sa execute cei N soldati.

Poveste şi cerinţă...

h2. Date de intrare

* linia 1: N K, reprezentand numarul de soldati, respectiv numarul de soldati chemati in fata.
* linia 2: S[~0~] S[~1~] ... S[~N-1~] (separate prin cate un spatiu)

Fişierul de intrare $soldiers.in$ ...

h2. Date de ieşire

In fisierul de iesire se va afla numarul cerut.
 
h2. Punctare

În fişierul de ieşire $soldiers.out$ ...

|_. Subtask |_. Punctaj |_. Constrangeri |
| 1         | 21 puncte  | 1 ≤ N ≤ 15 |
| 2         | 6 puncte  | 1 ≤ N ≤ 100   |
| 3         | 5 puncte  | 1 ≤ N ≤ 20 000
                          K ≤ 50 |
| 4         | 6 puncte  | 1 ≤ N ≤ 20 000
                          K ≤ 500 |
| 5         | 37 puncte | 1 ≤ N ≤ 200 000
                          k ≤ 5000         |
| 6         | 5 puncte  | 1 ≤ N ≤ 200 000
                           K=N             |
| 7         | 20 puncte | 1 ≤ N ≤ 200 000 |

h2. Restricţii

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. soldiers.in |_. soldiers.out |

|6 3
 6 1 5 2 4 3 | _0_ |
| 6 5
 6 1 5 2 4 3 | 4 |
|7 4
 4 5 1 7 2 6 3 | 6 |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

h3. Explicaţie

In primul exemplu, sergentul ii cheama pe cei  cu numerele 1, 2 si 3. Din fericire acestia se afla deja in ordinea corecta asa ca soldatii nu sunt obligati sa execute flotari.
 
In al doilea exemplu, din cauza soldatilor cu numerele 4 si 5 ordinea soldatilor nu mai este corecta corecta. Sergentul ii poate aranja in felul urmator folosind 4 interschimbari:
 
6 1 %{color:red}(5 2)% 4 3 -> 6 1 2 5 %{color:red}(4 3)% -> 6 1 2 %{color:red}(5 3)% 4 -> 6 1 2 3 %{color:red}(5 4)% -> 6 1 2 3 4 5
 
In cel de-al treilea exemplu, una din metodele de a ordona soldatii cu numere 1 2 3 si 4 folosind 6 interschimbari este:
%{color:red}(4,5)% 1 7 2 6 3 -> 5 4  1 7 2 %{color:red}(6,3)% -> 5 %{color:red}(4,1)% 7 2 3 6 -> 5 1 %{color:red}(4,7)% 2 3 6 -> 5 1 7 %{color:red}(4,2)% -> 5 1 7 2 %{color:red}(4,3)% 6 -> 5 1 7 2 3 4 6

...

== include(page="template/taskfooter" task_id="soldiers") ==