407985: GYM102956 M Brilliant Sequence of Umbrellas

Anton has $$$n$$$ umbrellas, each of them has a different number from $$$1$$$ to $$$n$$$ written on it. He wants to arrange some of the umbrellas in line so that they would form a brilliant sequence of umbrellas (BSU). A sequence of $$$k$$$ umbrellas with numbers $$$a_1, a_2, \ldots, a_k$$$ is considered a BSU if the following rules apply:

• $$$a_i > a_{i-1}$$$ for all $$$2 \le i \le k$$$;
• $$$\text{gcd}(a_i, a_{i-1}) > \text{gcd}(a_{i-1}, a_{i-2})$$$ for all $$$3 \le i \le k$$$. Here, $$$\text{gcd}(x, y)$$$ denotes the greatest common divisor of integers $$$x$$$ and $$$y$$$.

Anton would like to create a long BSU. Making the longest one doesn't bother him, he thinks that a BSU of length at least $$$\left\lceil\frac{2}{3}\sqrt{n}\right\rceil$$$ is quite enough.

Anton is busy reading fascinating books about lighthouses, so he asks you to find a BSU that would satisfy him.

The only line contains an integer $$$n$$$, the number of umbrellas ($$$1 \le n \le 10^{12}$$$).

The first line should contain an integer $$$k$$$, the length of the BSU you have found ($$$\left\lceil\frac{2}{3}\sqrt{n}\right\rceil \le k \le 10^6$$$).

The second line should contain $$$k$$$ integers $$$a_i$$$, the sequence itself ($$$1 \le a_i \le n$$$). The sequence should satisfy the rules mentioned above.

10

3
1 2 6 

22

4
1 2 6 15 

In the first example, $$$\left\lceil \frac{2}{3} \cdot \sqrt{10} \right\rceil = 3$$$, $$$\text{gcd}(2, 4) = 2$$$, $$$\text{gcd}(4, 8) = 4$$$.

In the second example, $$$\left\lceil \frac{2}{3} \cdot \sqrt{22} \right\rceil = 4$$$, $$$\text{gcd}(1, 6) = 1$$$, $$$\text{gcd}(6, 14) = 2$$$, $$$\text{gcd}(14, 21) = 7$$$.