Last Person Standing (Josephus Problem)

This problem is based on the famous Josephus problem. Given N people standing in a circle, every second person is eliminated until only one person remains. Your task is to determine the position of the last person standing.

The process can be defined recursively using the formula:

\(J(n)=\bigl(J(n-1)+2\bigr) \mod n\)

with the base condition \(J(1)=0\), and the final answer is \(J(n)+1\) because positions are numbered starting from 1.

inputFormat

The input is given via stdin and consists of a single integer N (1 ≤ N ≤ 10⁶), which represents the number of people in the circle.

outputFormat

Output the position of the last person standing to stdout as a single integer.

5

3