配点 : $400$ 点

問題文

すぬけ君は、渋谷の丸太やさんに丸太を買いに来ました。 すぬけ君は長さ $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$ 本ずつ手に入れるために必要な最小の金額を求めてください。

制約

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

入力

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

$n$

出力

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

4

3

例えば次のようにすると $3$ 円でほしい丸太がすべて手に入ります。

• 長さ $2,4,5$ の丸太を買う
• 長さ $5$ の丸太を切って 長さ $1$ の丸太 $2$ 本と長さ $3$ の丸太を作る
• 長さ $1$ の丸太を $1$ 本捨てる

109109109109109109

109109108641970782