1. You are given a number n, representing the size of array a. 2. You are given n numbers, representing elements of array a. 3. The array is nearly sorted. Every element is at-max displaced k spots left or right to it's position in the sorted array. Hence it is being called k-sorted array. 4. You are required to sort and print the sorted array. Note -> You can use at-max k extra space and nlogk time complexity.
Input Format
Input is managed for you
Output Format
Print the elements of sorted array in separate lines.
Constraints
1 <= n <= 30 0 <= n1, n2, .. n elements <= 100 0 < k <= n
Notice
Try First, Check Solution later
1. You should first read the question and watch the question video.2. Think of a solution approach, then try and submit the question on editor tab.3. We strongly advise you to watch the solution video for prescribed approach.Example
Input
9 3 2 4 1 6 5 7 9 8 3
Output
1 2 3 4 5 6 7 8 9