시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB24201694.118%

문제

FJ knows that the cows (like everyone else) love bonbons, which are very expensive candy. He has decided to purchase and give a single bonbon to one of his N (1 ≤ N ≤ 7,100,000) cows (which are conveniently numbered 1..N). He lines the cows up in order in a circle and starts with cow 1. He moves to cow 2 and asks her to leave the circle. He moves to cow 4 and asks her to leave. He continues to ask every other cow to leave the circle until only one remains -- and she gets the bonbon.

Determine which cow gets the bonbon.

입력

  • Line 1: A single integer: N

출력

  • Line 1: A single integer, the number of the cow that gets the bonbon.

예제 입력 1

7

예제 출력 1

7

힌트

Initial circle: 1 2 3 4 5 6 7 
Becomes:        1   3 4 5 6 7 
Becomes:        1   3   5 6 7 
Becomes:        1   3   5   7
Becomes:            3       7
Becomes:                    7