You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面背景

we are 伐木累

题目描述

光头坤是一个勤劳的伐木工人, 李老板需要 $n$ 根木材, 长度为 $1, 2, 3 \dots n$, 现在森林里恰好有 $n+1$ 棵大树, 每棵树的长度分别为 $1, 2, 3 \dots n+1$, 你在砍树后还可以将木头锯断, 比如长度为 $7$ 的树可以切割为 $1, 2, 4$ 三段木材.

现在我们想知道, 最少锯多少棵树, 即可满足李老板的要求?

输入格式

一行一个整数 $n$

输出格式

输出一个整数, 表示最少需要锯断多少树.

样例 #1

样例输入 #1

4

样例输出 #1

3

样例1解释

我们可以锯断 $2, 3, 5$ 的树, 这样 $5$ 的树可以分割为 $1, 4$, 就能满足李老板 $1, 2, 3, 4$ 的要求.

样例 #2

样例输入 #2

1000000000000000000

样例输出 #2

999999998585786440

提示

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