410058: GYM103934 F Indiana Jiang and the sphinx riddle

After years searching, Indiana Jiang's journey is reaching it's end. Right now, he is venturing into the most secret tomb in Egypt. However, Jiang didn't expected that his last challenge would be to solve the Sphinx's riddle! In the treasure chamber, at the feet of the sphinx, there is a chest, containing the artifacts Jiang has been searching for. Sphinxes are known to be treacherous, if Jiang doesn't win the challenge he may never leave the tomb.

The riddle goes like this. Initially, $$$N$$$ spheres numbered from one to $$$N$$$ are arranged in order. There are two mummies in the room, one with white stripes and one with black stripes, which will alternately take spheres until only one remains. The one with white stripes goes through the spheres from left to right, taking the balls alternately, that is, removing the second, fourth, sixth, etc.. After that, the mummy with black stripes goes through the sequence from right to left, also removing the spheres alternately, that is, remove the penultimate one and so on. As an example, consider that initially there are $$$7$$$ spheres. $$$$$$1\quad 2\quad 3\quad 4\quad 5\quad 6\quad 7$$$$$$ After the passage of the mummy with white stripes remains $$$$$$1\quad 3\quad 5\quad 7$$$$$$ After the passage of the mummy with black stripes remains $$$$$$3\quad 7$$$$$$ After the passage of the mummy with white stripes remains $$$$$$3$$$$$$ The result of the Sphinx's riddle is the number of the remaining sphere. So for $$$N = 7$$$ the answer is $$$3$$$.

The sphinx tells Jiang a number $$$N$$$ and wants to know the answer to the riddle. Jiang, who is not an amateur, has been communicating with you by radio the whole time. However, he doesn't have much time, help Jiang to solve the sphinx's riddle.

A single line containing a integer $$$N$$$ $$$(1 \leq N \leq 10^9)$$$, the initial number of spheres.

One integer, the answer to the sphinx riddle.

4

3

10

9