Không vượt ngưỡng (Smallest Prefix Reaching a Threshold)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho số nguyên dương $S$. Tìm số nguyên dương nhỏ nhất $n$ sao cho tổng $1+2+\cdots+n$ lớn hơn hoặc bằng $S$. Có thể tổng ở bước cuối vượt $S$; không cần bằng đúng $S$.

Input

Một số nguyên $S$ là ngưỡng cần đạt.

Output

In số nguyên dương $n$ nhỏ nhất thỏa yêu cầu.

Subtask

• Subtask 1 (20%): $1\le S\le10$.
• Subtask 2 (30%): $1\le S\le1000$.
• Subtask 3 (50%): $1\le S\le10^6$.

Ví dụ

Ví dụ 1

Input

10

Output

4

Giải thích

Tổng lần lượt sau n=1,2,3,4 là 1,3,6,10. Lần đầu tổng đạt 10 là n=4.

Ví dụ 2

Input

2

Output

2

Giải thích

Với n=1 tổng 1 vẫn nhỏ hơn 2; cộng tiếp 2 thành 3, vì 3>=2 nên n=2.