424. Henry's Binary Revolution

0

Medium

King Henry VIII desires to break away from the catholic church and revolutionize the decimal system. He seeks to implement the binary number system and tasks you with determining the count of 1s in the binary representation of each number up to a given number N. Your objective is to create an array ans of length n + 1, where ans[i] represents the number of 1s in the binary form of i (0 <= i <= n). Can you accomplish this in linear time O(n) and without utilizing any built-in functions?

Input Format

The first line contains an integer N, indicating the size of the array.

Output Format

Print an array ans, where each ans[i] represents the number of 1s in the binary representation of i.

Example

Input

5

Output

0 1 1 2 1 2

Constraints

0 <= n <= 10^5

Loading...

View Submissions

Console