D. Two Pirates - 2
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Two pirates are dividing looted treasures. There are $$$n$$$ treasures, the $$$i$$$-th of which costs $$$a_i$$$ gold. They move in rotation, each turn a pirate picks one of the remaining treasures. The thing is, the second pirate is drunk, so he doesn't make optimal picks and each turn just picks a random available treasure, uniformly. The first pirate knows that and always makes optimal picks.

Find the expected costs of treasures picked by both pirates.

Input

The first line contains an integer $$$n$$$ ($$$1 \le n \le 5000$$$) — the number of treasures.

The second line contains $$$n$$$ integers $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — the costs of the treasures.

Output

Output two floating-point numbers: the expected costs of treasures picked by the first and the second pirates.

The absolute or relative error of the numbers shouldn't exceed $$$10^{-9}$$$.

Examples
Input
2
1 3
Output
3.000000000000000 1.000000000000000
Input
3
2 1 4
Output
5.500000000000000 1.500000000000000