Beautiful Permutation

Difficulty: 1300 2000 ms 128 MB

math implementation

Output a permutation of 1..N where no two adjacent values differ by exactly 1 — specifically, print all EVEN numbers ascending, then all ODD numbers ascending. If no such permutation exists (N = 2 or 3), print NO SOLUTION.

Input: one integer N.

Output: the required permutation, or NO SOLUTION.

Constraints:

• 1 ≤ N ≤ 10⁵

Sample Tests

5

2 4 1 3 5

3

NO SOLUTION

Read the Editorial