# Problem D

Gini Stuðull

To calculate the coefficient for a group of people, the income of everyone in that group has to be known. If $y_1, y_2, \ldots , y_ n$ ($y_ i > 0$ for all $i$) denote the incomes of $n$ individuals the Gini coefficient of the group can be calculated using the formula: \[ G = \dfrac { \sum \limits _{i=1}^ n \sum \limits _{j=1}^ n \lvert y_ i - y_ j \rvert }{ 2 \sum \limits _{i=1}^ n \sum \limits _{j=1}^ n y_ i } \]

Here $\lvert x\rvert $ denotes the absolute value of $x$: $\lvert x\rvert = x$ if $x \geq 0$, but $\lvert x\rvert = -x$ if $x < 0$.

## Input

The first line of the input contains one integer $n$, the number of individuals in the group. Then there will be $n$ lines, one for each individual in the group, each containing an integer $0 < y_ i \leq 10^5$, the income of the $i$-th individual.

## Output

Output the Gini coefficient for the group. The output is considered correct if the relative or absolute error from the correct answer does not exceed $10^{-6}$. This means it does not matter how many significant digits the answer has as long as it’s accurate enough.

## Scoring

Group |
Points |
Constraints |

1 |
50 |
$n \leq 10^3$ |

2 |
50 |
$n \leq 10^5$ |

Sample Input 1 | Sample Output 1 |
---|---|

5 100 100 100 100 100 |
0.00000000000000000 |

Sample Input 2 | Sample Output 2 |
---|---|

5 400 100 300 200 500 |
0.26666666666666666 |

Sample Input 3 | Sample Output 3 |
---|---|

10 1 1 1 1 10000 1 1 1 1 1 |
0.89910080927165548 |