Se da o permutare a numerelor de la 1 la n. Se pot efectua cel mult K operatii de interschimbare a doua elemente alaturate din permutare. Care este cea mai mica permutare, in ordine lexicografica, ce poate fi obtinuta folosind cel mult K astfel de interschimbari?
- Date de intrare
- Pe prima linie se citeste numarul intreg n. Pe a doua linie se citesc n numere intregi, reprezentand permutarea initiala. Pe a treia linie se citeste numarul intreg K, numarul maxim de interschimbari alaturate permise.
- Date de iesire
- Se afiseaza cele n numere ale permutarii finale, separate prin spatiu.
- Restrictii
- 1 <= n <= 50 permutarea contine fiecare valoare de la 1 la n exact o data 0 <= K <= 100
Exemple
Exemplul 1
Intrare
10 9 1 2 6 5 4 3 7 10 8 5
Iesire
1 2 4 9 6 5 3 7 10 8
Exemplul 2
Intrare
5 5 4 3 2 1 0
Iesire
5 4 3 2 1