Find Total Cost

Each time, remove the current minimum and maximum elements of the array (they must be at two different positions) and insert their sum; the cost of this step is ceil((min+max)/(max−min+1)). Repeat until only one element remains, and find the total cost. Negative values are also rounded up in the mathematical sense.

输入格式

The first line contains n, followed by n integers. The original has no numeric bounds; this site adds 1≤n≤200000, with elements in −1000000000..1000000000.

输出格式

Output a single integer answer.

样例 1

输入：

5
2 3 4 5 7

输出：

8

样例 2

输入：

2
-2 -2

输出：

-4

样例 3

输入：

3
-4 1 2

输出：

0

样例说明

The outputs of the three public examples are, in order: 8; -4; 0. These answers have been checked by independent enumeration or direct simulation.