Some unexpected incidents occurred during the village chief election. Due to Xiaochang and Xiaopeng violating election rules and being disqualified, Xiao Ming was ultimately elected as the new village chief. As a result, Xiao Ming decided to treat everyone to a meal together.
In Zhangjia Village, the local customs are quite bold; meals must involve drinking wine and playing a game called "Drink to the Finish".
To describe this game specifically: $$$n$$$ people sit in a circle, and the $$$i$$$-th person holds a die that can roll an integer between $$$[1,a_i]$$$ with equal probability.
The game proceeds in rounds. At the start of each round:
(1) All people who have not yet become "wine dazed" roll their dice once.
(2) Now, each person checks the numbers rolled by their left and right neighbors. Assuming their own rolled number is $$$x$$$, and their left and right neighbors' numbers are $$$a$$$ and $$$b$$$ respectively, then in this round they need to drink $$$\max(0,a-x)+\max(0,b-x)$$$ grams of wine.
(3) Those who roll $$$x=1$$$ in this round will become "wine dazed" and can no longer roll their dice. Their number is fixed at 1 thereafter.
(4) The game ends when everyone has become "wine dazed".
Xiao Ming is worried that everyone might drink too much, but also wants to know whether his wine tolerance can last until the game ends. So he asks you to calculate: In this game, how many grams of wine is each person expected to drink?
The first line contains an integer $$$n$$$, representing the number of participants in the game.
The second line contains $$$n$$$ positive integers $$$a_1,\ldots,a_n$$$, listed clockwise to represent the parameters of each participant's die.
$$$3 \le n \le 10^5$$$
$$$1 \le a_i \le 10^5$$$
Output one line containing $$$n$$$ integers, representing the expected amount of wine each person $$$1,2,\ldots,n$$$ will drink respectively.
It can be proved that each answer can be expressed as a fraction $$$\frac{x}{y}$$$ ($$$\gcd(x,y)=1$$$). You only need to output $$$x \times y^{-1} \bmod 998244353$$$, where $$$y^{-1}$$$ is the unique integer satisfying $$$0 \lt y^{-1} \lt 998244353$$$ and $$$y \times y^{-1} \bmod 998244353 = 1$$$.
31 1 2
1 1 0
Clearly, the 3rd person won't drink any wine, while the 1st and 2nd persons drink equivalent amounts. All possible scenarios are:
$$$\frac{1}{2}$$$: $$$[1]$$$ – The game ends immediately (the left fraction represents probability).
$$$\frac{1}{4}$$$: $$$[2,1]$$$ – The 1st and 2nd persons need to drink $$$2-1=1$$$ unit of wine.
$$$\frac{1}{8}$$$: $$$[2,2,1]$$$ – The 1st and 2nd persons need to drink $$$2 \times (2-1)=2$$$ units of wine.
$$$\frac{1}{16}$$$: $$$[2,2,2,1]$$$ – The 1st and 2nd persons need to drink $$$3 \times (2-1)=3$$$ units of wine.
...
The answer can be easily calculated as $$$1 \times \frac{1}{4}+2 \times \frac{1}{8}+3 \times \frac{1}{16}+\ldots=1$$$.
