Write a program that takes in a non-negative integer k and a k-sorted array of integers and returns that sorted version of the array. Your function can sort the array in place. A k-sorted array is a partially sorted array in which all elements are at most k positions away from their sorted position.

For example, the array [3, 1, 2, 2] is k-sorted with k = 3, because each element in the array is at most 3 positions away from its sorted position.

Design and implement an algorithm to sort the array efficiently faster in O(nk) time complexity.

Your algorithm should take auxiliary space: O(1)

Input1

3

3 2 1 5 4 7 6 5

Output1

1 2 3 4 5 5 6 7

Input 2

3

6 5 3 2 8 10 9

Output2

2 3 5 6 8 9 10

Input 3

4

10 9 8 7 4 70 60 50

Output 3

4 7 8 9 10 50 60 70