Fişierul intrare/ieşire:	ksort.in, ksort.out	Sursă	Concursul National Urmasii lui Moisil 2011 - Clasa a 10-a
Autor	Cosmin-Mihai Tutunaru	Adăugată de	Andrici Cezar •andrici_cezar
Timp execuţie pe test	0.3 sec	Limită de memorie	36864 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Ksort

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

Date de intrare

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.

Date de ieşire

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.

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.

Exemplu

Cum se trimit solutii?