Tiệc trà điên rồ (Crazy Tea Party)

Nguồn: UVa

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $n$ người ngồi quanh một bàn tròn. Trong mỗi phút, ta được chọn đúng một cặp người đang ngồi cạnh nhau và đổi chỗ cho họ.

Hãy tìm số phút ít nhất cần thiết để đảo ngược thứ tự vòng tròn của tất cả người tham dự: người từng ở bên trái của một người phải trở thành người ở bên phải của người đó và ngược lại.

Input

Một số nguyên $n$, là số người tham dự.

Output

In thời gian nhỏ nhất, tính bằng phút, để đạt thứ tự ngược.

Subtask

• Subtask 1 (20%): $n\le20$.
• Subtask 2 (30%): $n$ chẵn và $22\le n\le32766$.
• Subtask 3 (50%): Đầy đủ: $1\le n\le32767$.

Ví dụ

Input

4

Output

2

Giải thích

Viết thứ tự ban đầu quanh bàn, bắt đầu từ người 1, là 1 2 3 4. Thứ tự đảo ngược tương ứng là 1 4 3 2.

Có thể đạt thứ tự này trong hai phút:

• Đổi chỗ hai người 1 và 2. Khi quay cách viết để bắt đầu lại từ 1, thứ tự là 1 3 4 2.
• Lúc này 3 và 4 ngồi cạnh nhau; đổi chỗ họ, ta được 1 4 3 2.

Không thể hoàn thành chỉ bằng một lần đổi chỗ, vì từ thứ tự ban đầu cần hoán đổi vị trí tương đối của 2 và 4, nhưng hai người này không ngồi cạnh nhau. Do đó thời gian nhỏ nhất là 2.