405150: GYM101807 B Bob the Builder

Bob the builder wants to build the most exciting roller coaster in the world!

Due to the limited space, Bob can only build the railroad without turning left or right. Also, Bob thinks the only interesting part of roller coaster is going down, so he will not consider any parts of the railroad going upward as well.

Under the above conditions, you may consider the railroad as a polyline (broken line) on a 2D Cartesian coordinate plane. Formally, Bob has to build the railroad from $$$x=0$$$ to $$$x=N$$$. For each integer $$$x=i$$$ ($$$0\le i\le N$$$), Bob can choose the height $$$H_i$$$ of the railroad as any non-negative integer. In other words, the railroad is a polyline formed by the points $$$(0, H_0), (1, H_1), \dots, (N, H_N)$$$ (in this order), with the constraints that:

• For safety reasons, the railroad should not be too steep, so for integers $$$i$$$ ($$$0\le i<N$$$), $$$H_{i + 1}=H_i$$$ or $$$H_{i + 1}=H_i - 1$$$.
• To let the passengers leave on the ground, $$$H_N=0$$$.

An example with $$$N=9$$$ and $$$H_{0..9}=\{4, 4, 3, 3, 3, 2, 2, 1, 1, 0\}$$$

To build an exciting roller coaster, Bob defines the exciting index as the number of times the passengers seeing new furthest part of the railroad. Formally:

• The passengers ride in positive $$$x$$$ direction (i.e. from $$$x=0$$$ to $$$x=N$$$), along the railroad.
• For integers $$$i$$$ ($$$0\le i\le N$$$), when passengers are at the point $$$(i, H_i)$$$, the furthest part of railroad they can see is defined the largest integer $$$f_i$$$ ($$$i\le f_i\le N$$$) such that there DO NOT EXIST any integers $$$j$$$ ($$$i< j< f_i$$$) that the point $$$(j, H_j)$$$ is strictly above the line segment formed by $$$(i, H_i)$$$ and $$$(f_i, H_{f_i})$$$. In this example, passengers at the point $$$(1, H_1)$$$ cannot see the point $$$(6, H_6)$$$ as there exists point $$$(4, H_4)$$$ lying strictly above the line segment formed by $$$(1, H_1)$$$ and $$$(6, H_6)$$$. However, they can see the point $$$(4, H_4)$$$ as there are no points lying strictly above the line segment formed by $$$(1, H_1)$$$ and $$$(4, H_4)$$$.

• For integers $$$i$$$ ($$$0\le i\le N$$$), if the value of $$$f_i$$$ is strictly greater than $$$f_k$$$ for all integers $$$k$$$ ($$$0\le k<i$$$), then point $$$(i, H_i)$$$ is considered as an exciting point. In particular, $$$(0, H_0)$$$ is an exciting point.
• The exciting index of the railroad is the number of exciting points.

An example with $$$f_{0..9}=\{1, 4, 4, 4, 8, 6, 8, 8, 9, 9\}$$$ and exciting index = 4

(Note that $$$f_4=8$$$ as $$$(6, 2)$$$ is just lying on the line segment formed by $$$(4, 3)$$$ and $$$(8, 1)$$$, but NOT "strictly above")

Given the value of $$$N$$$, please write a program to help Bob finding any valid design maximizing the exciting index.

The only line contains a single integer $$$N$$$ ($$$1\le N\le 10^6$$$).

On the first line, output the maximum exciting index.

On the next line, output $$$H_0, H_1, \dots H_N$$$, representing the design of the railroad.

9

4
4 4 3 3 3 2 2 1 1 0