Recamán

题目描述

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

数列的第一项 a1是 1；

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

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

输入格式

第一行，一个正整数n 。

输出格式

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

样例

输入样例 1

输出样例 1

输入样例 2

输出样例 2

样例解释

数据范围

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