Hoán vị của n là các dãy p gồm n phần tử phân biệt từ 1 đến n. Ví dụ [1, 2, 3], [3, 1, 2], [2, 3, 1] là hoán vị của 3, trong khi [1, 2], [3, 4, 2] thì không. Và với mỗi số nguyên dương n, ta sẽ có tất cả n! hoán vị.
Cho số nguyên dương n, hãy tìm hoán vị p của n thỏa mãn:
- Tồn tại một cặp (i, j) thỏa mãn p_i > p_j và i < j.
- \sum_{i = 1}^n gcd(i, p_{n-i+1}) đạt giá trị nhỏ nhất.
Input and Output
Input
- Số nguyên dương n (1 \le n \le 10^6).
Output
- In ra hoán vị p của n bất kỳ thỏa mãn.
Test
Input
4
Output
3 4 1 2
Note
- Với hoán vị p trên, ta có \sum_{i = 1}^4 gcd(i, p_{n-i+1}) = 4 là nhỏ nhất.
- Lưu ý rằng không chỉ có hoán vị p trên mới là đáp án đúng.
Bình luận