시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 20 6 4 25.000%

문제

Browsing Wikipedia and reading some random references are the best way to write problems.

Find a subset S ∈ {1, 2, . . . , n} such that:

  • For all pairs (a, b) such that a, b ∈ S and a < b, the values of bitwise XOR of a and b should be distinct.
  • |S| ≥ ⌊√(0.5n)⌋.

입력

The first line contains an integer n (1 ≤ n ≤ 107).

출력

The first line contains an integer m: the size of S.

The second line contains m distinct integers from 1 to n: the elements of the set S in any order.

예제 입력 1

49

예제 출력 1

4
1 2 3 4