育华学校的魔法宝石实验

题目描述

在育华学校的魔法兴趣小组中，同学们正在进行一项有趣的魔法宝石实验。有一种神奇的宝石，一对宝石可以用两种方法裂变成一对略有差异的宝石。初始时，有两块大小相同的宝石，每块的大小都是 1 单位。同学们希望通过一系列的操作，使得一对大小都是 1 单位的宝石，至少有一块宝石的大小等于目标大小 $n$ 单位。

操作规则如下：

• 裂变操作一：可以将一对大小为 $x, y$ 的宝石裂变成一对大小为 $x + y, y$ 的宝石。
• 裂变操作二：可以将一对大小为 $x, y$ 的宝石裂变成一对大小为 $x, x + y$ 的宝石。

输入格式

第一行输入一个正整数 $n$，表示目标宝石的大小。

输出格式

输出一个整数，表示达到目标所需的最少操作次数。

样例输入 #1

2

样例输出 #1

1

数据范围

对于 40% 的数据，$1 ≤ n ≤ 1000$。 对于 100% 的数据，$1 ≤ n ≤ 10^5$。