Description

小吴最近发现了有趣的 Recamán 数列，这个数列是这样生成数列的：

• 第一项 a1是1

• 如果${a_{k−1}}−k$是正整数并且没有在数列中出现过，那么数列的第 k 项$a_k={a_{k−1}}−k$, 否则为${a_{k−1}}+k$。

小吴想知道 Recamán 数列的前 n 项从小到大排序后的结果。

手动计算非常困难，小吴希望你能帮他解决这个问题。

Input Format

第一行，一个正整数n

Output Format

一行， n个空格分隔的整数，表示 Recamán 数列的前 n 项从小到大排序后的结果

5

1 2 3 6 7

8

1 2 3 6 7 12 13 20

Hint

样例解释 对于样例1,n=5: ·a1=1; ·a₁-2=-1,不是正整数，因此a2=a1+2=3; ·a₂-3=0,不是正整数，因此a3=a₂+3=6; ·a3-4=2,是正整数，且没有在数列中出现过，因此a₄=2; ·a₄-5=-3,不是正整数，因此 ·a₅=4+5=7; a1,a2,a3,Q4,as从小到大排序后的结果为12367。 对于所有数据点，保证1≤n≤3000。

Source