一个正 $n$ 边形 $P$ 可以通过添加连接 $P$ 的两个顶点且互不相交的线段，将其划分为 $n-2$ 个三角形。例如，正方形可以划分为两个三角形，正五边形可以划分为三个三角形，正六边形可以划分为四个三角形。所得的三角形集合称为 $P$ 的一个三角剖分。如果 $n$ 大于 3，则 $P$ 存在两种或多种不同的三角剖分。

一旦选定了 $P$ 的一个三角剖分 $T$，定义 $T$ 中两个三角形 $a$ 和 $b$ 之间的距离为从 $a$ 到 $b$ 移动时穿过相邻三角形边界的跳数。注意，在移动过程中必须始终保持在多边形 $P$ 的内部，即不允许跨越 $P$ 的边界。

例如，图 J.1 所示的三角剖分中，$a$ 和 $d$ 之间的距离为 3，因为从 $a$ 到 $d$ 需要经过三角形 $a, b, c$ 和 $d$，并且必须跨越三角形之间的边界跳跃 3 次。

图 J.1 正六边形的三角剖分

三角剖分 $T$ 的直径定义为 $T$ 中所有三角形对之间距离的最大值。编写一个程序，求出一个正 $n$ 边形 $P$ 的三角剖分，使得其直径在所有可能的三角剖分中最小，并输出该最小直径。

输入格式

程序从标准输入读取数据。输入的第一行包含一个整数 $n$ ($3 \le n \le 1,000,000$)，表示正 $n$ 边形的边数。

输出格式

程序将结果写入标准输出。输出仅一行，包含正 $n$ 边形三角剖分的最小直径。

样例

样例输入 1

3

样例输出 1

0

样例输入 2

4

样例输出 2

1

样例输入 3

6

样例输出 3

2