Maximum Permutation
Contest: Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 3500
Tags: constructive algorithms

Ecrade bought a deck of cards numbered from $$$1$$$ to $$$n$$$. Let the value of a permutation $$$a$$$ of length $$$n$$$ be $$$\min\limits_{i = 1}^{n - k + 1}\ \sum\limits_{j = i}^{i + k - 1}a_j$$$.

Ecrade wants to find the most valuable one among all permutations of the cards. However, it seems a little difficult, so please help him!

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$)  — the number of test cases. The description of test cases follows.

The only line of each test case contains two integers $$$n,k$$$ ($$$4 \leq k < n \leq 10^5$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^6$$$.

Output format:
For each test case, output the largest possible value in the first line. Then in the second line, print $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ ($$$1 \le a_i \le n$$$, all $$$a_i$$$ are distinct)  — the elements of the permutation that has the largest value.

If there are multiple such permutations, output any of them.

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

Note:
In the first test case, $$$[1,4,5,3,2]$$$ has a value of $$$13$$$. It can be shown that no permutations of length $$$5$$$ have a value greater than $$$13$$$ when $$$k = 4$$$.

In the second test case, $$$[4,2,5,7,8,3,1,6]$$$ has a value of $$$18$$$. It can be shown that no permutations of length $$$8$$$ have a value greater than $$$18$$$ when $$$k = 4$$$.

Example input:
2
5 4
8 4

Example output:
13
1 4 5 3 2
18
4 2 5 7 8 3 1 6

Editorial:
When it seems to be hard to come up with the whole solution directly, simplified questions can often be a great helper. So first let us consider the case where $$$n$$$ is the multiple of $$$k$$$.
Let $$$t=\frac{n}{k}$$$.
What is the largest value one can obtain theoretically? Pick out $$$t$$$ subsegments $$$a_{[1:k]},a_{[k+1:2k]},\dots,a_{[n-k+1:n]}$$$, and one can see that the answer cannot be greater than the average value of the sum of each subsegment, that is $$$\frac{n(n+1)}{2t}=\frac{k(n+1)}{2}$$$.
#### Case 1: $$$k$$$ is even
If $$$k$$$ is even, one can construct $$$a=[1,n,2,n-1,3,n-2,\dots,\frac{n}{2},\frac{n}{2}+1]$$$ to reach the maximum value.
#### Case 2: $$$k$$$ is odd
For easy understanding let us put $$$a_{[1:k]},a_{[k+1:2k]},\dots,a_{[n-k+1:n]}$$$ into a $$$t\times k$$$ table from top to bottom like this:

Note that the difference value between two consecutive subsegments is equal to the difference value between two values in the same column in this table. It inspires us to fill in the last $$$k-3$$$ columns in an S-shaped way like this:

Then our goal is to split the remaining $$$3t$$$ numbers into $$$3$$$ groups and minimize the difference value between the sum of each group.
If $$$n$$$ is odd, the theoretical maximum value mentioned above is an integer, and the sum of each group must be equal to reach that value. Otherwise, the theoretical maximum value mentioned above is not an integer, and the sum of each group cannot be determined. So let us first consider the case where $$$n$$$ is odd. A feasible approach to split the numbers is as follows:
$$$$$$(1,\frac{3t+1}{2},3t),(3,\frac{3t-1}{2},3t-1),\dots,(t,t+1,\frac{5t+1}{2}),(2,2t,\frac{5t-1}{2}),(4,2t-1,\frac{5t-3}{2}),\dots,(t-1,\frac{3t+3}{2},2t+1)$$$$$$
Then fill them into the table:

Similarly, one can come up with an approach when $$$n$$$ is even:

Okay, it's time for us to go back to the original problem.
Let $$$n=qk+r\ (r,q\in \mathbb{N},1\le r<k)$$$.
Split $$$n$$$ elements like this:

As shown in the picture, there are $$$(q+1)$$$ red subsegments with $$$r$$$ elements each, and $$$q$$$ blue subsegments with $$$(k-r)$$$ elements each. What is the largest value one can obtain theoretically now? Pick out $$$q$$$ non-intersecting subsegments consisting of a whole red subsegment and a whole blue segement each, and one can see that the answer cannot be greater than the average value of the sum of each subsegment, that is the sum of $$$1 \thicksim n$$$ subtracted by the sum of any whole red subsegment, then divide by $$$q$$$. Similarly, the answer cannot be greater than the sum of $$$1 \thicksim n$$$ added by the sum of any whole blue subsegment, then divide by $$$(q+1)$$$.
Thus, our goal is to make the maximum sum of each red subsegment the minimum, and make the minimum sum of each blue subsegment the maximum. Now here comes an interesting claim: it can be proved that,
- If $$$r\neq 1$$$ and $$$k-r\neq 1$$$, one can fill the red subsegments using the method when $$$n$$$ is the multiple of $$$k$$$ (here $$$n'=(q+1)r,k'=r$$$ ) with $$$1\thicksim (q+1)r$$$, and the blue subsegments (here $$$n'=q(k-r),k'=k-r$$$ ) with the remaining numbers;
- If $$$r=1$$$, one can fill the red subsegments with $$$1\thicksim (q+1)$$$ from left to right, and the first element of the blue subsegments with $$$(q+2)\thicksim (2q+1)$$$ from right to left, and the blue subsegments without the first element using the method when $$$n$$$ is the multiple of $$$k$$$ (here $$$n'=q(k-2),k'=k-2$$$ ) with the remaining numbers;
- If $$$k-r=1$$$ and $$$q=1$$$, one can let $$$a_k=n$$$, and fill the rest two subsegments using the method when $$$n$$$ is the multiple of $$$k$$$ (here $$$n'=n-1,k'=k-1$$$ ) with the remaining numbers;
- If $$$k-r=1$$$ and $$$q>1$$$, one can fill the blue subsegments with $$$(n-q+1)\thicksim n$$$ from right to left, and the first element of the red subsegments with $$$1\thicksim (q+1)$$$ from right to left, and the red subsegments without the first element using the method when $$$n$$$ is the multiple of $$$k$$$ (here $$$n'=(q+1)(r-1),k'=r-1$$$ ) with the remaining numbers,
then the constraints can both be satisfied and the value of the permutation is theoretically maximum. The proof is omitted here.
Time complexity: $$$O(\sum n)$$$
**Bonus: solve the problem if $$$k\ge 2$$$.**