Card 2

Interview

Time limit2sMemory limit128 MB

Summary

Simulate the Josephus-style card elimination process to find which card number remains last for a given N.

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

Problem

There are N cards in a stack. The cards are numbered from 1 through N from top to bottom, so card 1 is initially on top and card N is initially on the bottom.

Repeat the following two operations until only one card remains.

Discard the top card.
If any cards remain, move the new top card to the bottom of the stack.

When N = 4, the initial order is 1, 2, 3, 4. After discarding 1 and moving 2 to the bottom, the order becomes 3, 4, 2. Then discard 3 and move 4 to the bottom, leaving 2, 4. Finally, discard 2, and only card 4 remains.

Given N, find the number of the last remaining card.

Input

The first line contains an integer N. (1 ≤ N ≤ 500,000)

Output

Print the number of the last remaining card on the first line.

Examples1

Example 1
Input
```
6
```
Expected output
```
4
```