Crazy Tea Party

Source: UVa

Version: Phuoc Hung OJ Extended

Problem Statement

There are $n$ participants seated around a circular table. In each minute, exactly one pair of neighboring participants may swap places.

Find the minimum number of minutes required to reverse the circular order of all participants, so that every left neighbor becomes the corresponding right neighbor and vice versa.

Input

One integer $n$, the number of participants.

Output

Print the minimum required time in minutes.

Subtasks

• Subtask 1 (20%): $n\le20$.
• Subtask 2 (30%): $n$ is even and $22\le n\le32766$.
• Subtask 3 (50%): Full constraints: $1\le n\le32767$.

Examples

Input

4

Output

2

Explanation

Write the initial circular order starting from participant 1 as 1 2 3 4. The reversed order is 1 4 3 2.

It can be reached in two minutes:

• Swap neighboring participants 1 and 2. Rotating the written representation to start from 1 again gives 1 3 4 2.
• Participants 3 and 4 are now adjacent; swapping them gives 1 4 3 2.

One swap is not enough: relative to the initial order, participants 2 and 4 must exchange their positions, but they are not neighbors initially. Therefore the minimum time is 2.