Recamán Sequence

Problem Description

Xiaoyang recently discovered the interesting Recamán sequence, generated as follows:

• The first term $a_1$ is $1$.
• If $a_{k-1} - k$ is a positive integer and has never appeared in the sequence, then the $k$-th term $a_k = a_{k-1} - k$; otherwise $a_k = a_{k-1} + k$.

Xiaoyang wants the first $n$ terms of the Recamán sequence, sorted in ascending order. Manual calculation is very hard, so he hopes you can solve it for him.

Input Format

The first line contains one positive integer $n$.

Output Format

One line: $n$ integers separated by spaces, the first $n$ terms of the Recamán sequence sorted in ascending order.

Sample Input

Sample Input 1

5

Sample Input 2

8

Sample Output

Sample Output 1

1 2 3 6 7

Sample Output 2

1 2 3 6 7 12 13 20

Sample Explanation

For the first sample, $n = 5$, and the sequence is generated as:

• $a_1 = 1$;
• $a_1 - 2 = -1$, not a positive integer, so $a_2 = a_1 + 2 = 3$;
• $a_2 - 3 = 0$, not a positive integer, so $a_3 = a_2 + 3 = 6$;
• $a_3 - 4 = 2$, a positive integer and not yet in the sequence, so $a_4 = a_3 - 4 = 2$;
• $a_4 - 5 = -3$, not a positive integer, so $a_5 = a_4 + 5 = 7$.

The first $5$ terms are $1, 3, 6, 2, 7$; sorted ascending they become $1, 2, 3, 6, 7$, matching the output.

Constraints

For all test points, $1 \le n \le 3000$.