Hoán vị đẹp

Nguồn CSES Problem Set

Đề bài

Một hoán vị của các số nguyên $1,2,\ldots,n$ được gọi là đẹp nếu không có hai phần tử kề nhau nào có hiệu tuyệt đối bằng $1$.

Nói cách khác, với một hoán vị $p_1,p_2,\ldots,p_n$, điều kiện sau phải được thỏa mãn:

với mọi $1 \le i < n$.

Cho số nguyên $n$. Hãy xây dựng một hoán vị đẹp của các số nguyên $1,2,\ldots,n$ nếu tồn tại.

Input

Dòng duy nhất chứa số nguyên $n$ — số lượng phần tử của hoán vị.

Output

In ra một hoán vị đẹp của các số nguyên $1,2,\ldots,n$.

Nếu có nhiều hoán vị thỏa mãn, có thể in ra bất kỳ hoán vị nào.

Nếu không tồn tại hoán vị đẹp, in ra:

NO SOLUTION

Subtask

• Subtask 1 — 20%: $1 \le n \le 8$.
• Subtask 2 — 80%: $1 \le n \le 10^6$.

Ví dụ

Ví dụ 1

Input

5

Output

4 2 5 3 1

Explain

Dãy $4,2,5,3,1$ là một hoán vị của các số từ $1$ đến $5$ vì mỗi số $1,2,3,4,5$ xuất hiện đúng một lần.

Hiệu tuyệt đối giữa từng cặp phần tử kề nhau lần lượt là:

• $|4-2|=2$;
• $|2-5|=3$;
• $|5-3|=2$;
• $|3-1|=2$.

Không có hiệu nào bằng $1$, vì vậy đây là một hoán vị đẹp.

Ví dụ 2

Input

3

Output

NO SOLUTION

Explain

Với $n=3$, cần sắp xếp ba số $1,2,3$ sao cho không có hai số kề nhau nào có hiệu tuyệt đối bằng $1$.

Tuy nhiên, số $2$ có hiệu bằng $1$ với cả $1$ và $3$. Trong mọi cách sắp xếp ba phần tử, $2$ luôn phải đứng kề ít nhất một trong hai số này.

Do đó không tồn tại hoán vị đẹp của các số $1,2,3$, nên kết quả là NO SOLUTION.