Almost Equal
Contest: Codeforces Round 580 (Div. 1)
Difficulty rating: 1200
Tags: constructive algorithms, greedy, math

You are given integer $$$n$$$. You have to arrange numbers from $$$1$$$ to $$$2n$$$, using each of them exactly once, on the circle, so that the following condition would be satisfied:

For every $$$n$$$ consecutive numbers on the circle write their sum on the blackboard. Then any two of written on the blackboard $$$2n$$$ numbers differ not more than by $$$1$$$.

For example, choose $$$n = 3$$$. On the left you can see an example of a valid arrangement: $$$1 + 4 + 5 = 10$$$, $$$4 + 5 + 2 = 11$$$, $$$5 + 2 + 3 = 10$$$, $$$2 + 3 + 6 = 11$$$, $$$3 + 6 + 1 = 10$$$, $$$6 + 1 + 4 = 11$$$, any two numbers differ by at most $$$1$$$. On the right you can see an invalid arrangement: for example, $$$5 + 1 + 6 = 12$$$, and $$$3 + 2 + 4 = 9$$$, $$$9$$$ and $$$12$$$ differ more than by $$$1$$$.

Input format:
The first and the only line contain one integer $$$n$$$ ($$$1 \le n \le 10^5$$$).

Output format:
If there is no solution, output "NO" in the first line.

If there is a solution, output "YES" in the first line. In the second line output $$$2n$$$ numbers — numbers from $$$1$$$ to $$$2n$$$ in the order they will stay in the circle. Each number should appear only once. If there are several solutions, you can output any of them.

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

Note:
Example from the statement is shown for the first example.

It can be proved that there is no solution in the second example.

Example input:
3

Example output:
YES
1 4 5 2 3 6

Example input:
4

Example output:
NO

Editorial:
Consider a valid arrangement for some $$$ n $$$. We denote $$$ S_i = a_i + a_ {i + 1} + a_ {i + 2} + \dots + a_ {i + n-1} $$$ for each $$$ i $$$ from $$$ 1 $$$ to $$$ 2n $$$, where $$$ a_ {t + 2n} = a_ {t} $$$. Then we have: $$$ S_ {i + 1} -S_i = (a_ {i + 1} + a_ {i + 2} + a_ {i + 3} + \dots + a_ {i + n}) - (a_i + a_ {i + 1} + a_ {i + 2} + \dots + a_ {i + n-1}) = a_ {i + n} -a_i $$$. Hence $$$ | a_ {i + n} -a_i | \le 1 $$$. Since $$$ a_ {i + n} $$$ and $$$ a_i $$$ are different, $$$ | a_ {i + n} - a_i | = $$$ 1.
It is also clear from this that $$$ a_ {i + n} - a_i $$$ and $$$ a_ {i + n + 1} - a_ {i + 1} $$$ have opposite signs: if they were both equal to $$$ 1 $$$, we would get $$$ S_ {i + 2} - S_i = (S_ {i + 2} - S_ {i + 1}) + (S_ {i + 1} - S_i) = (a_ {i + n + 1} - a {i + 1 }) + (a_ {i + n} - a_i) = $$$ 2, similarly with $$$ -1 $$$. Thus, the values ​​$$$ a_ {i + n} -a_i $$$ for $$$ i $$$ from $$$ 1 $$$ to $$$ 2n $$$ shoul be $$$ 1 $$$ and $$$ -1 $$$ alternating, and this is a sufficient condition.
Now, if $$$ n $$$ is even, we get a contradiction, since $$$ a_ {i + n} - a_i = - (a _ {(i + n) + n} - a_ {i + n}) $$$, but due to the alternating they must be equal.
If $$$ n $$$ is odd, then it's now easy to build an example: for $$$ i $$$ from $$$ 1 $$$ to $$$ n $$$ $$$ a_i = 2i-1 $$$, $$$ a_i = 2i $$$, if $$$ i $$$ is even, and $$$ a_i = 2i $$$ , $$$ a_i = 2i-1 $$$ if $$$ i $$$ is odd.
Asymptotics $$$ O (n) $$$.
Challenge:
For which pairs of $$$ (n, k) $$$ ($$$ n> k \ge 1 $$$) is there an arrangement of numbers from $$$ 1 $$$ to $$$ n $$$ on a circle such that the sums of each $$$ k $$$ consecutive numbers differ by not more than $$$ 1 $$$ ?