World Tree Depth Difference

Odin discovered that after slaying the giant Ymir, a gigantic ash tree grew from his corpse. This tree forms the core of the universe and is known as the World Tree. Its branches construct the whole world and are guarded by mysterious arcane power. In the World Tree, each node has at most two children. The arcane power at a node is defined as follows:

• If a node has no children (a "source"), its arcane power is 1.
• If a node has one or two children, its arcane power is equal to max(child arcane powers) + 1.

Additionally, the tree satisfies a magical balance: at every node the absolute difference between the arcane powers of its left and right subtrees does not exceed 1. (If a node has only one child, the missing subtree is considered to have arcane power 0.)

Odin now wonders: In a World Tree with n nodes, what is the maximum possible difference between the depths of the highest and lowest sources (leaf nodes) among all trees satisfying these conditions?

Hints: It can be shown that the trees satisfying these conditions are equivalent to AVL trees with the following recurrence for the minimum number of nodes required for an AVL tree of height H:

[ N(1)=1,\quad N(2)=2, \quad N(H)=1+N(H-1)+N(H-2)\quad (H\ge3), ]

For a given n, let \(H_{max}\) be the largest integer such that \(N(H_{max})\le n\). In any AVL tree the leaves can only appear on two consecutive levels. A careful analysis shows that the maximum difference between the depths of the deepest leaf (at depth \(H_{max}\)) and the shallowest leaf is \(\lfloor (H_{max}-1)/2 \rfloor\>.

inputFormat

The input consists of a single integer n (1 ≤ n ≤ 10⁹), representing the number of nodes in the World Tree.

outputFormat

Output a single integer: the maximum difference in depth between the highest and lowest sources (leaf nodes) in any World Tree with n nodes that satisfies the above conditions.

sample

1

0