Codeforces Round 473 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

bitmasks

dp

graphs

implementation

math

*1900

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Mahmoud and Ehab and the xor-MST

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputEhab is interested in the bitwise-xor operation and the special graphs. Mahmoud gave him a problem that combines both. He has a complete graph consisting of *n* vertices numbered from 0 to *n* - 1. For all 0 ≤ *u* < *v* < *n*, vertex *u* and vertex *v* are connected with an undirected edge that has weight (where is the bitwise-xor operation). Can you find the weight of the minimum spanning tree of that graph?

You can read about complete graphs in https://en.wikipedia.org/wiki/Complete_graph

You can read about the minimum spanning tree in https://en.wikipedia.org/wiki/Minimum_spanning_tree

The weight of the minimum spanning tree is the sum of the weights on the edges included in it.

Input

The only line contains an integer *n* (2 ≤ *n* ≤ 10^{12}), the number of vertices in the graph.

Output

The only line contains an integer *x*, the weight of the graph's minimum spanning tree.

Example

Input

4

Output

4

Note

In the first sample: The weight of the minimum spanning tree is 1+2+1=4.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/14/2024 23:45:45 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|