Human Pyramid

Interview

Time limit1sMemory limit1024 MB

Summary

Given n people, find the tallest human pyramid they can build, where a pyramid of height h needs h(h+1)/2 people.

Level: Easy3 of 10
Topics: Math, Binary search
Solved: No attempts yet

Problem

As chairman of the Building A Pyramid Committee, you specialize in breaking one world record: building the highest human pyramid. Unfortunately, only a limited number of people are willing to be in the pyramid. Building human pyramids does not pay, so most people are volunteers.

A full human pyramid of height $h$ has $h$ layers of people. Seen from below, the first layer has $h$ people, the second has $h-1$ , the third has $h-2$ , and so on until the final layer has a single person. Given how many people are available, find the height of the highest pyramid these people can build.

Input

The input consists of one line with an integer $n$ ( $1 \leq n \leq 10^{12}$ ), the number of people available to build the pyramid.

Output

Output the height of the highest possible pyramid you can build with $n$ people.

Examples2

Example 1
Input
```
3
```
Expected output
```
2
```
Example 2
Input
```
12
```
Expected output
```
4
```