Lexicographic Smallest Array

★★★★★

2 votes

, Math, C++, Basic Math

Details

Problem

Given an array $A$ consisting of integers, find the lexicographically smallest array possible, if we can swap the elements of the array with a distance greater than or equal to $K$ .
Note: We can swap array $a_i$ and $a_j$ , if $|i - j| > K - 1$ .

Input:
The first line contains two positive integers $N$ and $K$ .
The next line contains an array consisting of $N$ integers.

Output:
The output should be the lexicographic smallest array possible after applying the operations.

Constraints:
$1 \leq N \leq 10^5$
$1 \leq K \leq N$
$1 \leq A_i \leq 10^9$

Sample Input

3 2
3 2 1

Sample Output

1 2 3

Time Limit: 2

Memory Limit: 256

Source Limit:

Explanation

In the first test case, we can swap(a[1], a[3]). The resulting array will be A[] = {1, 2, 3}.

Contributers:

Aditya Mittal

Divyam Agarwal