It doesn't get simpler!

Returning home from school, Ivan thought for a long time about that day's math club session, where the teacher talked about infinite number sequences. As one example, the teacher showed the following interesting sequence of positive integers: $\underbrace{\vphantom{,}1}, \underbrace{1, 2, 1}, \underbrace{1, 2, 3, 2, 1}, \underbrace{1, 2, 3, 4, 3, 2, 1}, ...$

The teacher explained that every positive integer appears infinitely many times in this sequence. Ivan, however, was curious about another question: how can you find the number at position $n$ of the sequence? The teacher said that this is very simple and suggested that Ivan work out the problem on his own.

Ivan likes programming as well as math, so he wants to implement an algorithm that answers this question quickly for very large values of $n$. Please help him.

The first line contains one integer $n$ ($1 \leq n \leq 10^{500\,000}$).

Print one integer without spaces and without leading zeros: the $n$-th element of the given sequence.

The jury does not guarantee that a solution exists that runs within twice the time limit on all tests.