   Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
Language:
A New Joseph Problem
 Time Limit: 4000MS Memory Limit: 131072K Total Submissions: 3904 Accepted: 916

Description

Newman and Bamboo are good friends. One day, Newman taught Bamboo the famous Joseph Problem: there are N persons numbered 1 to N standing round a circle. They stand clockwise according to their numbers (namely 1, 2, 3, 4, …, N). Then, starting from 1, the killer kills every 2nd person he counts until there is only one person left whose number is J(N). We can easily infer that J(1) = 1, J(5) = 3 and J(6) = 5. Bamboo finds this problem intriguing and starts thinking. Suddenly, he finds that if he continually uses J(N) to be the term in J, he can finally get a fixed number. For example, J(2) = 1, so J(J(2)) = 1, J(J(…J(2)…)) = 1. Newman agrees with Bamboo but Bamboo is not satisfied. Furthermore, Bamboo wants to know what the fixed number will be for a specific N. Can you help us?

Input

Only one line containing n (1 ≤ n ≤ 1010000).

Output

Only one line containing K such that J(J(J(JJ(N)…))) = K and J(K)=K.

Sample Input

`10`

Sample Output

`3`

Hint

J(10) = 5, J(5) = 3, J(3) = 3.

Source

[Submit]   [Go Back]   [Status]   [Discuss] Home Page Go Back To top