시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 31 15 14 53.846%

문제

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이 주어진다.

출력

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

예제 입력

6

예제 출력

6

힌트