题目描述

最近，你被恐怖的噩梦所困扰。在这些梦中，一群愤怒的Fenwick蜜蜂在轻重树枝交错的树上追逐你。你讨厌被它们烦人的刺叮咬。因此，你三天前决定制作一个捕梦网，但过程棘手，你无法弄清楚细节。

规划捕梦网变得如此压力山大，以至于你过去三个夜晚都失眠了，思考着长长的纱线、卡迈克尔数和几何。迄今为止唯一的进展是一些难以理解的图纸（见图 D.1）以及观察到跨越圆心角 $\theta$ 度、半径为 $r$ 的圆的弦长为 $2r \cdot \sin(\theta/2)$。但这有什么用呢？你宁愿再次梦见 Fenwick 蜜蜂，也不愿被这个可怕的项目多折磨一天。你需要立刻解决这个问题！

图 D.1：一个带有 $8$ 个凹口的捕梦网，展示了两种用纱线缠绕的方式。左边的捕梦网每个弦跨越 $2$ 个凹口，而右边的捕梦网每个弦跨越 $3$ 个凹口。

要制作捕梦网，你取一个有 $n$ 个等间距凹口的轮子，凹口从 $1$ 到 $n$ 编号。你用一根纱线缠绕这个轮子，每个弦跨越 $k$ 个凹口：从凹口 $1$ 开始，你重复地将纱线连接到前方 $k$ 个凹口，直到再次回到凹口 $1$。例如，当 $n = 8$ 且 $k = 3$ 时，你会从凹口 $1$ 到 $4$，然后 $7$、$2$、$5$、$8$、$3$、$6$、$1$。

捕梦网的效果取决于所用纱线的量。你需要选择 $k$，即每个弦跨越的凹口数，使得纱线的总长度最大化。答案不依赖于捕梦网的半径。

输入格式

输入包含：

• 一行，一个整数 $n$（$3 \leq n \leq 10^9$），表示轮子上的凹口数量。

输出格式

输出一个整数 $k$（$1 \leq k < n$），使得当每个弦跨越 $k$ 个凹口时，所用纱线的长度最大化。 如果有多个有效解，你可以输出其中任意一个。

8

3

5

2

6

5