카드 2

N장의 카드가 한 줄로 쌓여 있다. 카드에는 위에서부터 차례대로 1부터 N까지 번호가 붙어 있으며, 처음에는 1번 카드가 맨 위, N번 카드가 맨 아래에 있다.

카드가 한 장만 남을 때까지 다음 두 동작을 반복한다.

1. 맨 위의 카드를 버린다.
2. 남은 카드가 있다면, 새 맨 위 카드를 맨 아래로 옮긴다.

N = 4라면 처음 순서는 1, 2, 3, 4이다. 1을 버린 뒤 2를 아래로 옮기면 3, 4, 2가 되고, 이어서 3을 버리고 4를 아래로 옮기면 2, 4가 된다. 마지막으로 2를 버리면 4만 남는다.

N이 주어졌을 때 마지막에 남는 카드 번호를 구하시오.

첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 500,000)

첫째 줄에 마지막에 남는 카드의 번호를 출력한다.