Income Inequality

Time limit2sMemory limit1024 MB

Summary

Given n household wealth values, find the maximum of y minus x, where the top x percent of households hold y percent of total wealth.

Level: Medium5 of 10
Topics: Sorting, Prefix sum, Greedy
Solved: No attempts yet

Problem

According to Wikipedia, in 2021, the top 1% of households owned 32.3% of the wealth in the United States. More generally, for any percentage $x$ , the data may show that the top $x\%$ of households own $y\%$ of the wealth.

For any society with some inequality, $y > x$ holds except when $x = 0$ and $x = 100$ . Among all possible values of $x$ , what is the maximum value of $y - x$ ?

Given the incomes of all people in a society, find the maximum value of $y - x$ such that the top $x\%$ of people hold $y\%$ of the society's wealth.

Input

The first line contains a single integer $n$ ( $2 \le n \le 10^6$ ), the number of people in the society.

The second line contains $n$ integers. Each integer $m$ ( $1 \le m \le 10^{12}$ ) is the wealth of one household. The values are not necessarily distinct.

Output

Print the maximum possible value of $y - x$ , where the top $x\%$ of households own $y\%$ of the society's wealth. An answer is accepted if its absolute or relative error is within $10^{-6}$ .

Examples2

Example 1
Input
```
4
11 1 2 6
```
Expected output
```
35.000000
```
Example 2
Input
```
5
35 25 30 60 50
```
Expected output
```
15.000000
```