题目描述

白浅妹妹需要构造一个 1 ~ n 的排列 a1, a2, . . . , an 。 其中要求：

• 排列中顺序对和逆序对的数量相等。
• 输出符合上述要求的排列中字典序最小的方案。

下面定义顺序对和逆序对： 对于一组位置 (i, j)， 其中 i < j，若 ai < aj， 则构成顺序对； 若ai > aj， 则构成逆序对。

输入格式

一行一个正整数 n ，表示排列的长度。其中保证 n是 4 的整数倍。

输出格式

一行用空格分割的数字，表示答案的序列。

样例

输入

4

输出

1 4 3 2

提示