题目描述

给定一个整数 $N$。找到最小的正整数 $k$，使得 $(1+2+\\cdots+k)$ 是 $N$ 的倍数。可以证明这样的正整数 $k$ 总是存在。

约束条件

• $1 \\leq N \\leq 10^{15}$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$

输出

在一行中打印答案。

样例输入 1

11

样例输出 1

10

$1+2+\\cdots+10=55$ 成立，而 $55$ 确实是 $N=11$ 的倍数。没有满足条件的正整数 $k \\leq 9$，所以答案是 $k = 10$。

样例输入 2

20200920

样例输出 2

1100144