N개의 서로 다른 자연수로 이루어진 배열 A가 주어졌을 때, 이 배열을 사전식 순서 상 가장 뒷서는 배열로 정렬하는 프로그램을 작성하라. 단, 연속된 두 개의 원소만 교환할 수 있으며 원소 교환은 최대 S번 할 수 있다.
예를 들어, 5개의 자연수로 이루어진 배열 [3, 5, 2, 1, 4]가 주어지고 최대 2번 교환할 수 있으면 최종 정렬 결과는 [5, 3, 2, 1, 4]이다.
첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다.
둘째 줄에는 N개의 수가 차례대로 주어진다. 각 수는 1,000,000보다 작거나 같은 자연수이다.
마지막 줄에는 S가 주어진다. S는 1,000,000보다 작거나 같은 음이 아닌 정수이다.
정렬한 결과를 출력한다.
5
3 5 1 2 4
2
5 3 2 1 4
7
10 20 30 40 50 60 70
1
20 10 30 40 50 60 70
10
19 20 17 18 15 16 13 14 11 12
5
20 19 18 17 16 15 14 13 12 11
10
1 2 3 4 5 6 7 8 9 10
17
10 9 1 2 3 4 5 6 7 8
2
1000000 999999
1000000
1000000 999999