시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB61312960.417%

문제

N(1 ≤ n ≤ 32767)명의 사람들이 잔치에서 춤을 추게 되었다. 처음에는 1번부터 N번까지의 사람들이 차례대로, 둥글게 손을 잡고 서 있다. 그리고 춤이 끝날 때에는 이 순서가 반대(거꾸로, 뒤집힌)가 되어야 한다. 물론 사람들이 모두 손을 놓고 다시 자리를 잡으면 되겠지만, 그렇게 하면 둥그런 모양이 깨지게 된다. 따라서 자리를 바꿀 때에는, 서로 손을 잡고 있는 두 명의 사람만 자리를 바꿀 수 있다.

예를 들어 n=6인 경우를 보자. 맨 처음의 순서는 (1, 2, 3, 4, 5, 6)이 된다. 둥글게 서 있기 때문에 1번과 6번도 손을 잡고 있다. 이제 (1, 2, 3, 4, 5, 6) → (6, 2, 3, 4, 5, 1) → (2, 6, 3, 4, 5, 1) → (1, 6, 3, 4, 5, 2) → (1, 6, 3, 5, 4, 2) → (1, 6, 5, 3, 4, 2) → (1, 6, 5, 4, 3, 2)의 순서대로 바꾸면 자리가 반대가 된다. (6, 5, 4, 3, 2, 1)이 되는 게 맞겠지만, 어차피 둥글게 서 있기 때문에 (1, 6, 5, 4, 3, 2)와 같은 경우도 순서는 반대가 되는 게 맞다.

가급적이면 자리를 최소로 바꾸려고 한다. 최소로 자리를 바꾸려면 어떻게 해야 할까?

입력

첫째 줄에 n이 주어진다.

출력

첫째 줄에 최소 자리바꿈 회수를 출력한다.

예제 입력 1

6

예제 출력 1

6

예제 입력 2

5

예제 출력 2

4

예제 입력 3

4

예제 출력 3

2