Problem M. Mountain ≡

Statement

The mountain is represented by a binary heap with n vertices, there is also a number k, which represents the sum of distances between all pairs of vertices. Given the value of k, find n.

In this context, a binary heap is an undirected binary tree that satisfies the following conditions:

• Each vertex has at most three neighbors.
• The depth of all leaves (distance to the root) differs by no more than 1 layer.
• The last layer is filled from left to right without "holes".

For example, a binary heap with 4 vertices:

Input format

The input consists of a single line containing a natural number k.

Output format

Output n.

Constraints

0 ≤ k ≤ 10¹⁸

Пояснение к примеру

The distance between the 1st and 2nd vertices is 1. The distance between the 1st and 3rd vertices is 1. The distance between the 1st and 4th vertices is 2. The distance between the 2nd and 3rd vertices is 2. The distance between the 2nd and 4th vertices is 1. The distance between the 3rd and 4th vertices is 3. The sum of all distances is 1 + 1 + 2 + 2 + 1 + 3 = 10.

Sample tests

10

4