Last Remaining Player

In this problem, n players are arranged in a circle and numbered from 1 to n. The game proceeds in rounds and in each round, starting from the current player, the next immediate player in the circle is eliminated. After the elimination, the player following the eliminated one becomes the new current player, and the process continues until only one player remains.

More formally, let the players be indexed as \(1, 2, \ldots, n\). Starting with the first player (\(1\)), the elimination process is performed by removing the immediate next player in the circle (i.e. if the current index is \(i\), then remove the player at index \(i+1\) modulo the number of remaining players). This process continues until only one player is left. Your task is to determine the number assigned to the last remaining player.

inputFormat

The input consists of a single line containing one integer n (\(1 \le n \le 10^5\)), which represents the total number of players.

outputFormat

Output a single integer representing the number of the last remaining player.

5

3