← 返回题目列表

Codeforces · 340/C

C. 旅游问题

中文机器翻译题面 查看原题

Iahub 是游客的忠实粉丝。他想自己成为一名游客,所以他计划了一次旅行。一条笔直的道路上有 n 个 Iahub 想要访问的目的地。 Iahub 从 0 公里处开始行程。n 个目的地由非负整数序列 a1、a2、...、an 描述。数字ak代表第k个目的地距起点距离ak公里。没有两个目的地位于同一个地方。

Iahub 希望每个目的地仅访问一次。请注意,穿越目的地并不被视为访问,除非 Iahub 明确希望在该点访问该目的地。此外,在 Iahub 访问最后一个目的地后,他不会回到 0 公里,因为他在最后一个目的地停止了行程。

位于 x 公里处的目的地与位于 y 公里处的下一个目的地之间的距离为 |x - y|公里。我们将访问目的地的顺序称为“路线”。 Iahub 可以按他想要的任何顺序访问目的地,只要他访问了所有 n 个目的地并且访问某个目的地的次数不超过一次即可。

Iahub 开始在纸上写下所有可能的路线,并且对于每条路线,他都会记下他将行走的总距离。他感兴趣的是他选择路线时平均步行的公里数。当他厌倦了写出所有路线时,他请求你帮助他。

输入

第一行包含整数 n (2 ≤ n ≤ 105)。下一行包含 n 个不同的整数 a1, a2, ..., an (1 ≤ ai ≤ 107)。

输出

输出两个整数 - 等于所需平均数的分数的分子和分母。该分数必须是不可约的。

示例

输入 #1

3
2 3 5

输出 #1

22 3

注意

考虑 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 { 1 } { 6 } } \cdot ( 5 + 7 + 7 + 8 + 9 + 8 )$$ = $$\frac{44}{6}$$ = $$\frac{22}{3}$$。