Fax and his wingmate Flaco enjoying the party.

Fax McClad, Croneria's most festive bounty hunter, is hosting a big Christmas party in his neighbourhood! His neighbourhood can be thought of as a straight line.

Fax has ~N~ crew members he can invite. The ~i^\text{th}~ crew member is located ~x_i~ metres to the east of the origin. He would like to invite some of his crew members to attend his party, but he wants to minimize the amount of time wasted. In particular, if the party is located ~y~ metres to the east of the origin, then the ~i^\text{th}~ crew member will waste ~|x_i-y|^3~ time by going to the party.

Fax wants to invite all of his crew members to the party, but the total amount of time wasted might become too large. For each party size ~k~, what is the best location to host the party if Fax only invites the first ~k~ crew members? In other words, what is the value of ~y~ that minimizes:

$$\displaystyle |x_1-y|^3 + |x_2-y|^3 + \dots + |x_k-y|^3$$

Note: ~y~ can be a real number.

Constraints

~1 \le N \le 300\,000~

The absolute value of any coordinate will not exceed ~15\,000~. That is, ~|x_i| \le 15\,000~.

Subtask	Points	Additional Constraints
1	10	~0 \le x_i \le 1~ for all ~1 \le i \le N~
2	10	~N \le 30~
3	20	~N \le 900~
4	60	No additional constraints.

Input Specification

The first line will contain the integer ~N~.

On the next ~N~ lines, the ~i^\text{th}~ line will contain the integer ~x_i~.

Output Specification

There will be ~N~ lines of output. The ~k^\text{th}~ line of output will contain the best location to host the party if the first ~k~ of Fax's crew members are invited.

Your output will be judged as correct if the absolute error does not exceed ~10^{-3}~.

Sample Input

4
2823
5748
3092
-14068

Sample Output

2822.999999
4285.500000
4108.776249
-2600.293020