Throwing Cards Away II

Source: UVa

Version: Phuoc Hung OJ Extended

Problem Statement

An ordered deck contains $n$ cards numbered from $1$ to $n$, with card $1$ on top and card $n$ on the bottom.

While at least two cards remain, perform these operations in order:

1. discard the top card;
2. move the new top card to the bottom of the deck.

Find the last remaining card.

Input

One positive integer $n$.

Output

Print the number on the last remaining card.

Subtasks

• Subtask 1 (20%): $n\le100$.
• Subtask 2 (30%): $101\le n\le10000$.
• Subtask 3 (50%): Full constraints: $1\le n\le500000$.

Examples

Input

7

Output

6

Explanation

Start with 1 2 3 4 5 6 7. The deck changes as follows:

• Discard 1, then move 2 to the bottom: 3 4 5 6 7 2.
• Discard 3, then move 4 to the bottom: 5 6 7 2 4.
• Discard 5, then move 6 to the bottom: 7 2 4 6.
• Discard 7, then move 2 to the bottom: 4 6 2.
• Discard 4, then move 6 to the bottom: 2 6.
• Discard 2, leaving only card 6.

Therefore the program prints 6.