题目描述

整数 $N$ が与えられます． 正の整数 $k$ であって，$(1+2+\cdots+k)$ が $N$ の倍数になるもののうち， 最小のものを求めてください． なお，このような正の整数 $k$ が必ず存在することは証明できます．

输入格式

入力は以下の形式で標準入力から与えられる．

$N$

输出格式

答えを一行に出力せよ．

题目大意

给定 $n$，求最小的正整数 $k$，使得 $1 + 2 + \cdots + k$ 是 $n$ 的正整数倍。

11

10

20200920

1100144

提示

制約

• $1\ \leq\ N\ \leq\ 10^{15}$
• 入力は全て整数である．

Sample Explanation 1

$1+2+\cdots+10=55$ であり，これは確かに $N=11$ の倍数です． $k\ \leq\ 9$ で条件を満たすものは存在しないため，$k=10$ が答えになります．