B - log Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400

問題文

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

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

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

制約

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

入力

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

n

出力

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


入力例 1

4

出力例 1

3

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

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

入力例 2

109109109109109109

出力例 2

109109108641970782

Score : 400 points

Problem Statement

Snuke is visiting a shop in Tokyo called 109 to buy some logs. He wants n logs: one of length 1, one of length 2, ..., and one of length n. The shop has n+1 logs in stock: one of length 1, one of length 2, \dots, and one of length n+1. Each of these logs is sold for 1 yen (the currency of Japan).

He can cut these logs as many times as he wants after buying them. That is, he can get k logs of length L_1, \dots, L_k from a log of length L, where L = L_1 + \dots + L_k. He can also throw away unwanted logs.

Snuke wants to spend as little money as possible to get the logs he wants. Find the minimum amount of money needed to get n logs of length 1 to n.

Constraints

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

Input

Input is given from Standard Input in the following format:

n

Output

Print the minimum amount of money needed to get n logs of length 1 to n.


Sample Input 1

4

Sample Output 1

3

One way to get the logs he wants with 3 yen is:

  • Buy logs of length 2, 4, and 5.
  • Cut the log of length 5 into two logs of length 1 each and a log of length 3.
  • Throw away one of the logs of length 1.

Sample Input 2

109109109109109109

Sample Output 2

109109108641970782