Recamán数列

题目描述

小杨最近发现了有趣的Recamán数列，这个数列的生成规则如下：

• 数列的第一项 $a_1$ 是1；
• 对于第 $k$项$（k>1）$的计算规则：
  • 如果$a_{k-1} - k$是正整数且未在数列中出现过，则$a_k = a_{k-1} - k$；
  • 否则$a_k = a_{k-1} + k$。

小杨想请你计算Recamán数列的前$n$项从小到大排序后的结果。

输入格式

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

输出格式

输出一行$n$个空格分隔的整数，表示前$n$项从小到大排序后的结果。

样例

输入样例1

5

输出样例1

1 2 3 6 7

样例解释

对于样例1，$n=5$：

• $a_1 = 1$
• $a_2 = a_1 + 2 = 3$（因为$1-2=-1$不是正整数）
• $a_3 = a_2 + 3 = 6$（因为$3-3=0$不是正整数）
• $a_4 = a_3 - 4 = 2$（因为$6-4=2$是正整数且未出现过）
• $a_5 = a_4 + 5 = 7$（因为$2-5=-3$不是正整数） 排序结果为：1 2 3 6 7

数据范围

对于所有测试数据，保证$1 \leq n \leq 3000$。