题目描述

一个包含数字 $1, 2, \cdots, n$，且每个数字恰好出现一次的排列称为「美丽的」，当且仅当排列中不存在任意两个相邻元素的差值为 $1$。

给定一个整数 $n$，请判断是否存在一个「美丽的」排列。

输入格式

第一行包含一个正整数 $n$。

输出格式

如果存在「美丽的」排列，输出任意一种可能的排列。

如果不存在，输出 NO SOLUTION。

样例

5

4 2 5 3 1

数据范围与提示

• $1 \le n \le 10^6$
• 当 $n = 2$ 或 $n = 3$ 时，不存在美丽的排列。