Description

你的公司有\(n\)个妹子，她们要开演唱会，第\(i\)个人的迷之分数为\(a_i\)。观众对一组妹子的满意度定义为这些妹子迷之分数的平均数减去中位数。你需要选出一些妹子，使得观众的满意度最大。

Input

• 第一行一个正整数\(n\)，表示有\(n\)个妹子
• 第二行用空格隔开的\(n\)个整数\(a_1, a_2, ..., a_n\)

Output

• 仅一个实数x，表示最大满意度，保留4位小数

Sample

Input

4
1 2 3 12

Output

3.0000

Hint

• 对于30%的数据，\(n\le 10\)
• 对于40%的数据，\(n\le 5000\)
• 对于100%的数据，\(n\le 200000, 0\le a_i\le 10^9\)

Source

CoolZn Round III

zrO jkxing Orz