Sắp xếp nổi bọt (Bubble Sort)

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

Đề bài

Xét một hoán vị ngẫu nhiên của $n$ phần tử khác nhau và số lần đổi chỗ mà Bubble Sort thực hiện. Hãy tính kỳ vọng của số lần đổi chỗ.

Input

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

Mỗi file input của Phước Hưng OJ chứa đúng một test case.

Output

In kỳ vọng dưới dạng số nguyên hoặc phân số tối giản có mẫu $2$.

Subtask

• Subtask 1 (20%): $1\le n\le 100$.
• Subtask 2 (30%): $1\le n\le 10000$.
• Subtask 3 (50%): $1\le n\le 100000$.

Ví dụ

Input

3

Output

3/2

Giải thích

Có $3!=6$ hoán vị của ba phần tử. Số lần đổi chỗ Bubble Sort thực hiện trên sáu hoán vị tương ứng bằng số cặp phần tử đang ngược thứ tự; các giá trị là $0,1,1,2,2,3$.

Tổng là $9$, nên kỳ vọng bằng

Theo định dạng yêu cầu, kết quả được in là 3/2.