The team has been so focused on studying algorithms that they completely neglected the best kind of problems: those who require no classic algorithms at all! Fortunately, our friends at Yardi decided to help us give XORin, Lu-chan and Golgo a taste of what it's like to solve such a problem.

Given an integer N, find an array A of no more than 100 positive integers with the property that for each integer x (1 ≤ x ≤ N) there is at least one subarray of A whose sum is exactly x.


The first line of input contains integer N.


The first line of output should contain the number of elements in A.
The second line should contain all of A's elements, separated by a space.


  • 1 ≤ N ≤ 106
  • 1 ≤ t ≤ 106 for every t in A
  • It is guaranteed that at least one such array A exists.
  • Subarray = subset. For example {1, 3} is a subarray of {1, 2, 3}


1 2 3

Sponsors Gold