Smallest k in Natural Number Sum

Given a positive integer \(N\), your task is to determine the smallest positive integer \(k\) such that the sum of the first \(k\) natural numbers is at least \(N\). In mathematical terms, you need to find the minimum \(k\) satisfying the inequality:

\[ \frac{k(k+1)}{2} \ge N \]

For example, if \(N=10\), then \(1+2+3+4 = 10\) so the answer is \(k=4\); and if \(N=20\), then \(1+2+3+4+5+6 = 21\) so the answer is \(k=6\). The problem requires an efficient solution that can handle large inputs up to \(10^9\).

inputFormat

The input consists of a single line containing one integer \(N\) (\(1 \le N \le 10^9\)).

outputFormat

Output a single integer, the smallest \(k\) such that \(1+2+\cdots+k \ge N\).

10

4