Card 2

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.

1. Discard the top card.
2. 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.

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

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