#M. L2-5

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

让我们假设有一对数(a,b)。我们可以从前一步得到后一对数(a,a+b)或者(a+b,b)

让我们规定一开始这对数为(1,1)，你的任务就是找到数 $k$
使 $k$ 为从(1,1)转换到一对至少含有一个 $n$ 的数对的最少步骤

输入包含唯一的整数 $n (1 \le n \le 10^6)$

打印唯一的整数 $k$

(1,1) 可以通过三步转化为包含 5 ：(1,1) → (1,2) → (3,2) → (5,2)