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 urmarw vs roaga pe voi sa ii spuneti cate flotari trebuie sa execute cei N soldati.

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.

h2. Date de intrare

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

h2. Restricţii

h2. Punctare

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

|_. Subtask |_. Punctaj |_. Constrangeri |
| 1         | 6 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. Exemplu
table(example). |_. soldiers.in |_. soldiers.out |

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

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

h3. Explicaţie