CF340C Tourist Problem

Iahub 是一位旅游爱好者。他想成为一名旅行家，因此计划了一次旅行。有 $n$ 个目的地位于一条直线上，Iahub 想要全部参观。Iahub 从 $0$ 公里处出发。这 $n$ 个目的地由一个非负整数序列 $a_1, a_2, \ldots, a_n$ 描述。数字 $a_k$ 表示第 $k$ 个目的地距离起点 $a_k$ 公里。没有两个目的地位于同一点。 Iahub 希望每个目的地只访问一次。需要注意的是，仅经过某个目的地不视为访问，除非 Iahub 明确选择在那一时刻访问该地。此外，在访问完最后一个目的地后，他不会返回 $0$ 公里，而是直接结束旅程。 对于位于 $x$ 公里和 $y$ 公里的两个相邻目的地，它们之间的距离为 $|x-y|$ 公里。我们称一种访问顺序为“一条路线”。Iahub 可以以任意顺序访问所有 $n$ 个目的地，并且每个目的地最多访问一次。 Iahub 正在纸上写出所有可能的路线，并为每一条路线记录他将要行走的总距离。他想知道随机选择一条路线时，他平均要走多少公里。由于手写所有路线很繁琐，他请求你帮助他计算。

第一行包含整数 $n$（$2 \leq n \leq 10^5$）。下一行包含 $n$ 个互不相同的整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^7$）。

输出两个整数，表示所求平均值的最简分数形式的分子和分母。

考虑 $6$ 条可能的路线： - $[2, 3, 5]$：行走总距离：$|2-0| + |3-2| + |5-3| = 5$； - $[2, 5, 3]$：$|2-0| + |5-2| + |3-5| = 7$； - $[3, 2, 5]$：$|3-0| + |2-3| + |5-2| = 7$； - $[3, 5, 2]$：$|3-0| + |5-3| + |2-5| = 8$； - $[5, 2, 3]$：$|5-0| + |2-5| + |3-2| = 9$； - $[5, 3, 2]$：$|5-0| + |3-5| + |2-3| = 8$。 平均路线距离为 $\frac{5+7+7+8+9+8}{6} = \frac{44}{6} = \frac{22}{3}$。 由 ChatGPT 5 翻译