409665: GYM103677 C Raisin Box

The Sun-Maid is at her raisin factory, where this season's $$$n$$$ raisins are ready to be packaged and shipped worldwide to all the eager consumers.

All the raisins are lined up on the conveyor belt, one after the other, where raisin $$$i$$$ has size $$$s_i$$$. Since every raisin is special and unique, no two raisins have the same size ($$$s_i \neq s_j$$$ if $$$i \neq j$$$).

The first raisin box of the year is created by selecting a contiguous group of raisins of any size. Each potential raisin box (with distinct endpoints) can be made with equal probability.

The Sun-Maid must be careful not to upset the raisins by following a very specific set of traditions. The Sun-Maid has a tradition of eating the first box of raisins every year. When she opens the box, she carefully selects the largest raisin, awarding it the Specialest Raisin of the Year Award, sparing it from consumption.

Of course, each raisin would like to receive this incredibly prestigious award. Given each raisin's size, determine the probability that it's selected as the Specialest Raisin, multiplied by the total number of possible boxes, $$$\binom{n + 1}{2}$$$.

Note: Watch out for integer overflows.

The first line contains a single integer, $$$2 \leq n \leq 10^5$$$, the number of raisins.

The second line contains $$$n$$$ integers, where $$$1 \leq s_i \leq 10^9$$$ is the $$$i$$$-th raisin's size.

The only line of output should contain $$$n$$$ integers, where the $$$i$$$-th value is the probability that raisin $$$i$$$ is the Specialest Raisin, multiplied by $$$\binom{n + 1}{2}$$$.

4
2 4 1 3

1 6 1 2