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.

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 soldatu nu sunt asezati corect, va incepe sa ordoneze soldatii. El ii va ordona pe cei K soldati folosind interschimbari adiacenti. La fiecare pas va alege 2 soldati aflati in ordine consecutive (din cei n) si ii va obliga sa isi interschimve 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.

h2. Punctare
|_. Subtask |_. Punctaj |_. Constrangeri |

| 1         | 21 puncte  | 1 ≤ N ≤ 15 |

| 1         | 6 puncte  | 1 ≤ N ≤ 15 |

| 2         | 6 puncte  | 1 ≤ N ≤ 100   |
| 3         | 5 puncte  | 1 ≤ N ≤ 20 000
                          K ≤ 50 |

table(example). |_. soldiers.in |_. soldiers.out |
|6 3

 6 1 5 2 4 3 | _0_ |

 6 1 5 2 4 3 | 0 |

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