Smallest Prefix Reaching a Threshold

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Given positive S, find the smallest positive n such that 1+2+...+n is at least S. The sum may exceed S.

Input

One positive integer S, the target threshold.

Output

Print the minimum qualifying positive integer n.

Subtasks

• Subtask 1 (20%): 1 <= S <= 10.
• Subtask 2 (30%): 1 <= S <= 1000.
• Subtask 3 (50%): 1 <= S <= 1000000.

Examples

Example 1

Input

10

Output

4

Explanation

The prefix sums are 1,3,6,10; n=4 is the first to reach 10.

Example 2

Input

2

Output

2

Explanation

At n=1 the sum is 1; at n=2 it becomes 3, meeting the target.