Guiguzi’s Minimal Coin Bags

Guiguzi was a very clever strategist who was always busy. One day, on his journey in Xiānyáng, a friend told him that the largest auction house in the city was holding an auction. One particular treasure, the Wordless Heavenly Book, caught his eye. However, his schedule was tight and his long‐distance carriage ticket to Handan was booked for a time when the auction was nearly over. Therefore, he decided to prepare in advance by counting his coins and packing them into small money bags. His goal was to be able to pay any amount of coins using a combination of these sealed (and non‐openable) money bags.

Being extra frugal, Guiguzi wanted to use as few bags as possible under the condition that, apart from bags containing exactly 1 coin (duplicates of 1 are allowed), no two bags contain the same number of coins if that number is greater than \(1\) (i.e. for any coin count \(c>1\), it appears in at most one bag).

Given that he has a total of \(m\) coins, can you determine the minimum number of bags he will use and how many coins will go into each bag? The coins in each bag cannot be divided further; however, they can be used in combination to form any payment between \(1\) and \(m\) coins.

Note on Validity: The set of bag values must be such that every integer in the range \([1, m]\) can be represented as the sum of a subset of these bag coin counts. The bag counts greater than \(1\) must all be distinct, though multiple bags with 1 coin are allowed.

inputFormat

The input is a single integer \(m\) (\(1 \le m \le 10^9\)) representing the total number of coins.

For example:

5

outputFormat

On the first line, output the minimum number of bags required. On the next line, output the number of coins in each bag (in the order they are used) separated by a space.

For example, for the sample input above a valid output is:

3
1 1 3

sample

1

1
1