ksort

Ksort

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

Poveste şi cerinţă...

Începând de anul acesta, Ţirbi este TeamLead la o organizaţie necunoscută (încă) dar pe care acesta încearcă să o scoată din anonimat. De aceea el lansează următoarea provocare: dat un vector cu {$N$} elemente distincte, să se transforme într-un vector {$K-sortat$}. Un vector se numeşte {$K-sortat$} dacă are exact {$K$} elemente pe aceleaşi poziţii ca şi în vectorul sortat crescător. Singurul tip de operaţie permisă asupra vectorului este {$swap(i,j)$} care schimbă între ele elementele de pe poziţiile {$i$} şi {$j$}.
 
Deoarece Ţirbi este foarte ocupat, vă dă vouă un vector cu {$N$} elemente, şi vă roagă să îl transformaţi într-un vector {$K-sortat$} cu un număr minim de operaţii {$swap$}.

h2. Date de intrare

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

Fişierul de intrare $ksort.in$ conţine pe prima linie numerele naturale $N$ şi $K$ separate printr-un singur spaţiu, iar pe linia următoare, $N$ numere naturale distincte separate prin câte un singur spaţiu.

h2. Date de ieşire

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

Fişierul de ieşire $ksort.out$ va conţine pe prima linie numărul minim de operaţii $swap$ efectuate. Pe liniile următoare se descriu aceste operaţii, câte una pe linie, prin precizarea poziţiilor elementelor ce se schimbă între ele. Dacă nu există soluţie, se va scrie $-1$ pe prima linie în fişierul de ieşire.

h2. Restricţii

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

* $3 ≤ N ≤ 100000$
* $1 ≤ K ≤ N$
* Toate valorile din vector sunt distincte două câte două şi mai mici sau egale decât $2 000 000 000$.

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

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

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

|

h3. Explicaţie
 
...
 

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

7324