两个海盗正在瓜分掠夺来的宝藏。一共有 $n$ 件宝藏，其中第 $i$ 件宝藏的价值为 $a_i$ 金币。他们轮流行动，每轮一名海盗会从剩下的宝藏中挑选一件。问题在于，第二个海盗喝醉了，所以他不会做出最优选择，而是每轮等概率随机挑选一件当前可用的宝藏。第一个海盗知道这一点，并且总是做出最优的选择。
求两个海盗各自获得的宝藏价值的期望值。
输入格式
第一行包含一个整数 $n$ ($1 \le n \le 5000$) —— 宝藏的数量。
第二行包含 $n$ 个整数 $a_i$ ($1 \le a_i \le 10^9$) —— 每件宝藏的价值。
输出格式
输出两个浮点数：分别表示第一个海盗和第二个海盗获得的宝藏价值的期望值。
答案的绝对误差或相对误差不应超过 $10^{-9}$。
样例
输入样例 1
2 1 3
输出样例 1
3.000000000000000 1.000000000000000
输入样例 2
3 2 1 4
输出样例 2
5.500000000000000 1.500000000000000