Bonbons

Interview

Time limit1sMemory limit1024 MB

Summary

Given N cows in a circle where every second remaining cow leaves, find the number of the last cow standing.

Level: Medium4 of 10
Topics: Math, Simulation
Solved: No attempts yet

Problem

FJ knows that the cows (like everyone else) love bonbons, which are very expensive candy. He has decided to buy one bonbon and give it to one of his $N$ cows ( $1 \le N \le 7,100,000$ ). The cows are numbered 1 to $N$ and stand in order in a circle, starting with cow 1. He moves to cow 2 and asks her to leave the circle. He moves to cow 4 and asks her to leave. He continues to ask every other cow to leave until only one remains, and that cow gets the bonbon.

Determine which cow gets the bonbon.

Input

A single integer $N$ .

Output

A single integer, the number of the cow that gets the bonbon.

Hint

Initial circle: 1 2 3 4 5 6 7 
Becomes:        1   3 4 5 6 7 
Becomes:        1   3   5 6 7 
Becomes:        1   3   5   7
Becomes:            3       7
Becomes:                    7

Examples1

Example 1
Input
```
7
```
Expected output
```
7
```