圆木

时间限制：2s
空间限制：1024MB

题目描述

商店里有长度分别为 $1,2,\ldots,n+1$ 的 $n+1$ 根圆木，每种长度恰好一根，且每根的价格都是 $1$ 元。你希望得到长度分别为 $1,2,\ldots,n$ 的 $n$ 根圆木。

购买后，你可以任意多次切割圆木：若 $L=L_1+L_2+\cdots+L_k$，就可以把一根长度为 $L$ 的圆木切成长度分别为 $L_1,L_2,\ldots,L_k$ 的 $k$ 根圆木。也可以丢弃不需要的圆木。

求得到所有目标圆木所需的最小花费。

输入格式

输入一个整数 $n$。

输出格式

输出所需的最小花费。

样例输入 1

4

样例输出 1

3

样例说明 1

例如，可以购买长度为 $2,4,5$ 的圆木，把长度为 $5$ 的圆木切成 $1,1,3$，再丢弃多余的一根长度为 $1$ 的圆木。

样例输入 2

109109109109109109

样例输出 2

109109108641970782

数据范围

• $1\le n\le 10^{18}$。