题目描述

すぬけ君は、渋谷の丸太やさんに丸太を買いに来ました。 すぬけ君は長さ $1$ から $n$ までの $n$ 種類の丸太が $1$ 本ずつほしいです。 丸太やさんには、長さ $1$ から $n+1$ までの $n+1$ 種類の丸太がそれぞれ $1$ 円で売られています。どの丸太の在庫も $1$ 本ずつしかありません。

すぬけ君は買った丸太を切る作業を好きなだけ行えます。つまり、$L\ =\ L_1\ +\ \dots\ +\ L_k$ であるとき、長さ $L$ の丸太 $1$ 本から、長さ $L_1,\ \dots,\ L_k$ の $k$ 本の丸太を作る作業を何度でもできます。また、不要な丸太を捨てることができます。

すぬけ君はできるだけ安く丸太を手に入れたいです。 長さ $1$ から $n$ までの $n$ 種類の丸太を $1$ 本ずつ手に入れるために必要な最小の金額を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$n$

输出格式

長さ $1$ から $n$ までの $n$ 種類の丸太を $1$ 本ずつ手に入れるための最小金額を出力せよ。

题目大意

Snuke 正在前往一家名为 109 的商店购买木材。 他想要 $n$ 段木材，长度依次为 $1,2…n$。 商店库存有 $n+1$ 段木材，长度依次为 $1,2…n+1$。 每段售价 $1$ 元。

购买后，他可以随意切割木材。 也就是说，他可以将一段长为 $L$ 的木材切成任意 $k$ 段，只要这 $k$ 段的总长度恰好等于 $L$ 。他还可以扔掉不需要的木材。

Snuke 想花尽可能少的钱来获得他想要的木材，于是他请你帮忙计算一下最少的花费。

4

3

109109109109109109

109109108641970782

提示

制約

• $1\ \leq\ n\ \leq\ 10^{18}$

Sample Explanation 1

例えば次のようにすると $3$ 円でほしい丸太がすべて手に入ります。 - 長さ $2,4,5$ の丸太を買う - 長さ $5$ の丸太を切って 長さ $1$ の丸太 $2$ 本と長さ $3$ の丸太を作る - 長さ $1$ の丸太を $1$ 本捨てる