C0408 Recamán

Recamán

题目描述

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

数列的第一项 a1是 1；

如果 a_k-1-k 是正整数并且没有在数列中出现过，那么数列的第 k项ak 为a_k-1-k ，否则为 a_k-1+k

小杨想知道 Recamán 数列的前 n项从小到大排序后的结果。手动计算非常困难，小杨希望你能帮他解决这个问题。

输入格式

第一行，一个正整数n 。

输出格式

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

样例

输入样例 1

5

输出样例 1

1 2 3 6 7

输入样例 2

8

输出样例 2

1 2 3 6 7 12 13 20

样例解释

对于样例1，n = 5:

• a₁ = 1
• a₁ - 2 = -1（不是正整数），因此 a₂ = a₁ + 2 = 3
• a₂ - 3 = 0（不是正整数），因此 a₃ = a₂ + 3 = 6
• a₃ - 4 = 2（是正整数且未出现过），因此 a₄ = a₃-4 = 2
• a₄ - 5 = -3（不是正整数），因此 a₅ = a₄ + 5 = 7

a₁,a₂,a₃,a₄,a₅从小到大排序后的结果为1 2 3 6 7

数据范围

对于所有数据点，保证1≤n≤3000。