Given a sequence of n integers arr, determine the lexicographically smallest sequence which may be obtained from it after performing at most k element swaps, each involving a pair of consecutive elements in the sequence.

Note: A list x is lexicographically smaller than a different equal-length list y if and only if, for the earliest index at which the two lists differ, x’s element at that index is smaller than y’s element at that index.

Signature

int[] findMinArray(int[] arr, int k)

Input

n is in the range [1, 1000].

Each element of arr is in the range [1, 1,000,000].

k is in the range [1, 1000].

Output

Return an array of n integers output, the lexicographically smallest sequence achievable after at most k swaps.

Example 1

n = 3

k = 2

arr = [5, 3, 1]

output = [1, 5, 3]

We can swap the 2nd and 3rd elements, followed by the 1st and 2nd elements, to end up with the sequence [1, 5, 3]. This is the lexicographically smallest sequence achievable after at most 2 swaps.

Example 2

n = 5

k = 3

arr = [8, 9, 11, 2, 1]

output = [2, 8, 9, 11, 1]

We can swap [11, 2], followed by [9, 2], then [8, 2].

func findMinArray(arr: [Int], k: Int) -> [Int] {
	var newArray = arr
	var newK = k
	// iterate through the number of swaps available
	while newK > 0 {
		// find the minimum available element from first index to kth index
		var minimumElement = Int.max
		for current in 1...newK {
			print(current)
			if current < newArray.count && newArray[current] < minimumElement {
				minimumElement = newArray[current]
			}
		}
		print("newK", newK)
		// important
		// swap this minimum element with the previous element
		// since we can only swap adjacent elements
		if newK < newArray.count {
			newArray.swapAt(newK-1, newK)
		}
		newK -= 1
	}
	return newArray;
}

var arr = [5,3,1]
//var arr = [8, 9, 11, 2, 1]
print(findMinArray(arr: arr, k: 3))