Reconstruct the Original Deck

Given an integer \(n\), there are \(n\) cards numbered from \(1\) to \(n\). Initially, the cards are arranged in an unknown order in a deck. A process is performed as follows:

• If the deck has at least two cards, take the top card and move it to the bottom of the deck, then remove the new top card and output it.
• If only one card remains, output it directly.

The sequence of output cards turns out to be \(1,2,\ldots,n\) (in that order). Your task is to reconstruct the original order of the deck (from top to bottom) before the process began.

Hint: You can reverse the process. Let the output sequence be \(a_1, a_2, \ldots, a_n\) where \(a_1=1, a_2=2, \ldots, a_n=n\). The reverse procedure is:

[ \text{Initialize } D \text{ with } [a_n]. ]

Then, for \(r\) taking the values \(a_{n-1}, a_{n-2}, \ldots, a_1\) in that order, do:

[ \textbf{if } D \neq \emptyset: \quad x = \text{remove the last element of } D; \quad \text{insert } x \text{ at the beginning of } D; \quad \text{then insert } r \text{ into the second position of } D. ]

The resulting deck \(D\) will be the original deck order.

inputFormat

The input consists of a single integer \(n\) representing the number of cards.

outputFormat

Output the original deck order as \(n\) space-separated integers (from top to bottom).

sample

1

1