Fedya and Array
Contest: Codeforces Round 852 (Div. 2)
Difficulty rating: 1100
Tags: constructive algorithms, math

For his birthday recently Fedya was given an array $$$a$$$ of $$$n$$$ integers arranged in a circle, For each pair of neighboring numbers ($$$a_1$$$ and $$$a_2$$$, $$$a_2$$$ and $$$a_3$$$, $$$\ldots$$$, $$$a_{n - 1}$$$ and $$$a_n$$$, $$$a_n$$$ and $$$a_1$$$) the absolute difference between them is equal to $$$1$$$.

Let's call a local maximum an element, which is greater than both of its neighboring elements. Also call a local minimum an element, which is less than both of its neighboring elements. Note, that elements $$$a_1$$$ and $$$a_n$$$ are neighboring elements.

Unfortunately, Fedya lost an array, but he remembered in it the sum of local maximums $$$x$$$ and the sum of local minimums $$$y$$$.

Given $$$x$$$ and $$$y$$$, help Fedya find any matching array of minimum length.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). Description of the test cases follows.

Each line of each test case contain two integers $$$x$$$ and $$$y$$$ ($$$-10^{9} \le y < x \le 10^{9}$$$) — the sum of local maximums and the sum of local minimums, respectively.

Output format:
For each test case, in the first line print one integer $$$n$$$ — the minimum length of matching arrays.

In the second line print $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^{9} \leqslant a_i \leqslant 10^{9}$$$) — the array elements such that the the absolute difference between each pair of neighboring is equal to $$$1$$$.

If there are multiple solutions, print any of them.

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

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

Note:
In the first test case, the local maximums are the numbers at $$$3, 7$$$ and $$$10$$$ positions, and the local minimums are the numbers at $$$1, 6$$$ and $$$8$$$ positions. $$$x = a_3 + a_7 + a_{10} = 2 + 0 + 1 = 3$$$, $$$y = a_1 + a_6 + a_8 = 0 + (-1) + (-1) = -2$$$.

In the second test case, the local maximums are the numbers at $$$2$$$ and $$$10$$$ positions, and the local minimums are the numbers at $$$1$$$ and $$$3$$$ positions. $$$x = a_2 + a_{10} = -1 + 5 = 4$$$, $$$y = a_1 + a_3 = -2 + (-2) = -4$$$.

In the third test case, the local maximums are the numbers at $$$1$$$ and $$$5$$$ positions, and the local minimums are the numbers at $$$3$$$ and $$$6$$$ positions.

Example input:
4
3 -2
4 -4
2 -1
5 -3

Example output:
10
0 1 2 1 0 -1 0 -1 0 1
16
-2 -1 -2 -1 0 1 2 3 4 5 4 3 2 1 0 -1 
6
1 0 -1 0 1 0
16
2 3 2 1 0 -1 0 -1 0 -1 0 1 2 1 0 1

Editorial:
Note that the local minimums and maximums will alternate, and there will be the same number of them $$$k$$$. Let's call the $$$i$$$-th local maximum by $$$a_i$$$, the $$$i$$$-th local minimum by $$$b_i$$$. Without loss of generality, consider that $$$a_i$$$ goes before $$$b_i$$$. To get $$$b_i$$$ from $$$a_i$$$ we need to write out $$$a_i - b_i$$$ numbers, to get $$$a_{(i + 1) \bmod k}$$$ from $$$b_i$$$ we need to write out $$$a_{(i + 1) \bmod k} - b_i$$$ numbers.
Thus, $$$(a_1 - b_1) + (a_2 - b_1) + (a_2 - b_2) + \ldots + (a_k - b_k) + (a_1 - b_k) = 2 \cdot (a_1 + a_2 + \ldots + a_k) - 2 \cdot (b_1 + b_2 + \ldots + b_k) = 2 \cdot (A - B) = n$$$
The array $$$[y, y + 1, y + 2, \ldots, x - 1, x, x - 1, x - 2, \ldots, y + 1]$$$ will satisfy the condition.