Practice Sequences with the exercise "Remaining Card"

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Sequences

Statement

Goal

You have N cards in a stack. Each card has a different number written on it.

The top card is written 1. The second card is written 2. The third card is written 3...
The sequence continues to the last card (the bottom card) which is written N.

Repeat the following operations until the stack of cards is reduced to 1 card:
➀ throw away the top card
② move the current top card to the bottom

You got one last card in hand. What is the number written on it?

Input

Line 1: an integer N

Output

Line 1: the number on the remaining card

Constraints

1 ≤ N ≤ 1,000,000,000

Be aware of the very high upper limit. Design a fast algorithm to solve it.

Example

Input

Output

Solve it

A higher resolution is required to access the IDE