순환선

시간 제한1초메모리 제한1024 MB

요약

n개 역이 같은 간격으로 놓인 순환선에서 임의의 역 X에 대해 A까지의 거리와 B까지의 거리 쌍이 X를 유일하게 결정하도록 하는 서로 다른 두 역 A, B의 순서쌍 개수를 구한다.

문제

안드레이와 보리스가 사는 도시의 지하철은 순환선 하나로 이루어져 있다. 이 선을 따라 같은 간격으로 n개의 역이 놓여 있고, 역에는 1부터 n까지 번호가 붙어 있다. 인접한 두 역 사이의 구간을 역간 구간이라고 한다.

순환선의 열차는 시계 방향과 반시계 방향 양쪽으로 다니므로, 한 역에서 다른 역으로 갈 때 승객은 더 적은 수의 역간 구간을 지나는 방향을 고를 수 있다. 한 역에서 다른 역으로 가는 데 지나야 하는 역간 구간 수의 최솟값을 두 역 사이의 거리라고 하자.

두 친구는 다음 조건이 성립함을 알아냈다. 어떤 역 X를 정해 두 수, 즉 안드레이가 사는 역에서 역 X까지의 거리 Da와 보리스가 사는 역에서 역 X까지의 거리 Db를 적으면, 얻은 두 수의 쌍 [Da, Db]가 역 X를 유일하게 결정한다.

예를 들어 n = 4이고 안드레이가 1번 역, 보리스가 2번 역에 살면 1번 역은 쌍 [0, 1]로, 2번 역은 쌍 [1, 0]으로, 3번 역은 쌍 [2, 1]로, 4번 역은 쌍 [1, 2]로 정해진다.

두 사람의 같은 반 친구 세르게이는 옆 도시에 살아서 안드레이와 보리스가 어느 역에 사는지 모른다. 친구들을 찾아 나선 세르게이는 안드레이가 역 A에 살고 보리스가 역 B에 살 때 위 조건이 성립하는 역의 쌍 A, B가 몇 가지인지 궁금해졌다.

순환선의 역 수 n이 주어질 때 가능한 경우의 수를 구하는 프로그램을 작성하시오.

첫째 줄에 정수 n이 주어진다 (3 ≤ n ≤ 40 000).

가능한 경우의 수를 한 줄에 출력한다.

첫 번째 예제에서는 다음 경우가 성립한다.