CSES - Permutations | Hoán vị

Xem PDF

Điểm: 1000 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Một hoán vị của các số nguyên \(1, 2, 3, \ldots, n\) được gọi là đẹp nếu không có hai phần tử liền kề nào chênh lệch đúng \(1\) đơn vị.

Cho số nguyên dương \(n\), hãy tìm một hoán vị đẹp nếu tồn tại một dãy như thế.

Input

  • Chỉ một dòng duy nhất chứa số nguyên dương \(n\).

Output

  • In ra một hoán vị đẹp của các số tự nhiên \(1, 2, 3, \ldots, n\). Nếu có nhiều kết quả, hãy in ra một hoán vị bất kì. Nếu không có hoán vị thoả mãn, hãy in ra NO SOLUTION.

Constraints

  • \(1 \le n \le 10^6\)

Example

Sample input 1

5

Sample output 1
4 2 5 3 1

Sample input 2

3

Sample output 2
NO SOLUTION


Bình luận