Bảng nhân (Multiplication Table)

Nguồn: CSES

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

Đề bài

Xét bảng nhân $n\times n$. Với $1\le i,j\le n$, ô ở hàng $i$, cột $j$ có giá trị:

Giả sử $n$ là số lẻ. Lấy toàn bộ $n^2$ giá trị của bảng, giữ nguyên số lần xuất hiện của các giá trị trùng nhau, rồi sắp xếp không giảm. Hãy tìm phần tử ở chính giữa.

Vị trí giữa theo đánh số từ $1$ là:

Input

Một dòng chứa số nguyên lẻ $n$.

Output

In giá trị trung vị của bảng nhân.

Subtask

• Subtask 1 — 20%: $n\le101$.
• Subtask 2 — 30%: $n\le10001$.
• Subtask 3 — 50%: $1\le n<10^6$, $n$ lẻ.

Ví dụ

Input

3

Output

3

Giải thích

Bảng khi $n=3$ là:

Dãy sau khi sắp xếp là $1,2,2,3,3,4,6,6,9$. Phần tử thứ $5$ là $3$.