No More Inversions
Contest: Educational Codeforces Round 102 (Rated for Div. 2)
Difficulty rating: 1500
Tags: constructive algorithms, math

You have a sequence $$$a$$$ with $$$n$$$ elements $$$1, 2, 3, \dots, k - 1, k, k - 1, k - 2, \dots, k - (n - k)$$$ ($$$k \le n < 2k$$$).

Let's call as inversion in $$$a$$$ a pair of indices $$$i < j$$$ such that $$$a[i] > a[j]$$$.

Suppose, you have some permutation $$$p$$$ of size $$$k$$$ and you build a sequence $$$b$$$ of size $$$n$$$ in the following manner: $$$b[i] = p[a[i]]$$$.

Your goal is to find such permutation $$$p$$$ that the total number of inversions in $$$b$$$ doesn't exceed the total number of inversions in $$$a$$$, and $$$b$$$ is lexicographically maximum.

Small reminder: the sequence of $$$k$$$ integers is called a permutation if it contains all integers from $$$1$$$ to $$$k$$$ exactly once.

Another small reminder: a sequence $$$s$$$ is lexicographically smaller than another sequence $$$t$$$, if either $$$s$$$ is a prefix of $$$t$$$, or for the first $$$i$$$ such that $$$s_i \ne t_i$$$, $$$s_i < t_i$$$ holds (in the first position that these sequences are different, $$$s$$$ has smaller number than $$$t$$$).

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The first and only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$k \le n < 2k$$$; $$$1 \le k \le 10^5$$$) — the length of the sequence $$$a$$$ and its maximum.

It's guaranteed that the total sum of $$$k$$$ over test cases doesn't exceed $$$10^5$$$.

Output format:
For each test case, print $$$k$$$ integers — the permutation $$$p$$$ which maximizes $$$b$$$ lexicographically without increasing the total number of inversions.

It can be proven that $$$p$$$ exists and is unique.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the sequence $$$a = [1]$$$, there is only one permutation $$$p = [1]$$$.

In the second test case, the sequence $$$a = [1, 2]$$$. There is no inversion in $$$a$$$, so there is only one permutation $$$p = [1, 2]$$$ which doesn't increase the number of inversions.

In the third test case, $$$a = [1, 2, 1]$$$ and has $$$1$$$ inversion. If we use $$$p = [2, 1]$$$, then $$$b = [p[a[1]], p[a[2]], p[a[3]]] = [2, 1, 2]$$$ and also has $$$1$$$ inversion.

In the fourth test case, $$$a = [1, 2, 3, 2]$$$, and since $$$p = [1, 3, 2]$$$ then $$$b = [1, 3, 2, 3]$$$. Both $$$a$$$ and $$$b$$$ have $$$1$$$ inversion and $$$b$$$ is the lexicographically maximum.

Example input:
4
1 1
2 2
3 2
4 3

Example output:
1 
1 2 
2 1 
1 3 2

Editorial:
At first, let's look at sequence $$$s$$$: $$$s_1, s_2, \dots, s_{p - 1}, s_{p}, s_{p - 1}, \dots s_2, s_1$$$. Let's prove that the number of inversions in $$$s$$$ is the same regardless of what $$$s_i$$$ are (the only condition is that $$$s_i$$$ should be distinct).
Let's group all elements $$$s_i$$$ by their value — there will be $$$1$$$ or $$$2$$$ elements in each group. Then we can take any two groups with values $$$x$$$ and $$$y$$$ and calculate the number of inversions between elements in these groups. It's easy to note that construction will always be like $$$\dots x, \dots, y, \dots, y, \dots, x \dots$$$ (or $$$\dots x, \dots, y, \dots, x \dots$$$) and regardless of $$$x > y$$$ or $$$x < y$$$ in both cases there will be exactly two inversions between groups equal to $$$x$$$ and to $$$y$$$ (or one inversion in the second case). So the total number of inversion will be equal to $$$2 \frac{(p - 1)(p - 2)}{2} + (p - 1) = (p - 1)^2$$$.
Now we can split sequences $$$a$$$ and $$$b$$$ into two parts. Let $$$m = n - k$$$, then the first part is elements from segment $$$[1, k - m - 1]$$$ and the second is from $$$[k - m, k + m]$$$. Note that the second parts both in $$$a$$$ and $$$b$$$ are exactly the sequence $$$s$$$ described above.
The total number of inversions is equal to the sum of inversions in the first part, in the second part, and the inversions with elements from both parts. Note that in $$$a$$$ the first and the third components are equal to $$$0$$$ and the second component is constant, so in $$$b$$$ we must also have $$$0$$$ inversions in the first part and $$$0$$$ inversion between parts.
It means that $$$b$$$ must start from $$$1, 2, \dots, (k - m - 1)$$$. But since the number of inversions in the second part is constant we can set the remaining elements the way we want. And since we want to build lexicographically maximum $$$b$$$, we should make the second part as $$$k, k - 1, \dots, (k - m + 1), (k - m), (k - m + 1), \dots, k$$$.
In the end, optimal $$$b$$$ is $$$1, 2, \dots, (k - m - 1), k, (k - 1), \dots, (k - m + 1), (k - m), (k - m + 1), \dots, k$$$. The permutation $$$p$$$ to make such $$$b$$$ is equal to $$$1, 2, \dots, (k - m - 1), k, (k - 1), \dots, (k - m)$$$.