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}$$。