D - Caracal vs Monster

Score : $400$ points

Problem Statement

Caracal is fighting with a monster.

The health of the monster is $H$.

Caracal can attack by choosing one monster. When a monster is attacked, depending on that monster's health, the following happens:

• If the monster's health is $1$, it drops to $0$.
• If the monster's health, $X$, is greater than $1$, that monster disappears. Then, two new monsters appear, each with the health of $\lfloor X/2 \rfloor$.

($\lfloor r \rfloor$ denotes the greatest integer not exceeding $r$.)

Caracal wins when the healths of all existing monsters become $0$ or below.

Find the minimum number of attacks Caracal needs to make before winning.

Constraints

• $1 \leq H \leq 10^{12}$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$H$

Output

Find the minimum number of attacks Caracal needs to make before winning.

2

3

When Caracal attacks the initial monster, it disappears, and two monsters appear, each with the health of $1$.

Then, Caracal can attack each of these new monsters once and win with a total of three attacks.

4

7

1000000000000

1099511627775