E. Probabilistic Card Game
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Alice and Bob have a deck of cards, which is initially empty. They play a game that lasts for $$$m$$$ rounds. In the $$$i$$$-th round, the following events occur:

  • a card with the value $$$a_i$$$ is added to the deck (it is guaranteed that no card with this value was previously in the deck);
  • if there are fewer than $$$3$$$ cards in the deck, the round ends;
  • otherwise, Alice chooses a card from the deck;
  • then Bob chooses a card (knowing which card Alice chose; he cannot choose the same one);
  • one more card is chosen from the remaining $$$i-2$$$ cards uniformly at random;
  • at the end, all three chosen cards are returned to the deck.

Let $$$a$$$ be the value on Alice's card, $$$b$$$ be the value on Bob's card, and $$$c$$$ be the value on the randomly chosen card. Then Bob receives:

  • $$$0$$$ points if $$$|a - c| \le |b - c|$$$ (where $$$|x|$$$ denotes the absolute value of $$$x$$$);
  • $$$0$$$ points if card $$$c$$$ is between cards $$$a$$$ and $$$b$$$ (i. e., $$$a \lt c \lt b$$$ or $$$b \lt c \lt a$$$);
  • $$$|b-c|$$$ points otherwise.

Alice's goal in each round is to minimize Bob's expected score, while Bob's goal is to maximize it. What will be the expected score for Bob in each round if both Alice and Bob play optimally? Print the expected score modulo $$$998\,244\,353$$$.

Note that the players minimize or maximize the real value of the expected score, not the result taken modulo $$$998\,244\,353$$$.

Input

The first line contains a single integer ($$$3 \le m \le 2 \cdot 10^5$$$) — the number of rounds.

The second line contains $$$m$$$ integers $$$a_1, a_2, \dots, a_m$$$ ($$$1 \le a_i \le 10^{12}$$$; all $$$a_i$$$ are distinct).

Output

Print $$$m-2$$$ integers: the $$$i$$$-th number should be equal to the expected score for Bob in the round $$$i+2$$$ with optimal play from both players modulo $$$998\,244\,353$$$ (i. e., let the expected score be an irreducible fraction $$$\frac{x}{y}$$$; you need to output $$$x \cdot y^{-1} \bmod 998\,244\,353$$$, where $$$y^{-1}$$$ is such a number that $$$y \cdot y^{-1} \bmod 998\,244\,353 = 1$$$).

Note that the players minimize or maximize the real value of the expected score, not the result taken modulo $$$998\,244\,353$$$.

Examples
Input
5
1 10 3 11 7
Output
0
499122177
665496236
Input
6
23 7 11 24 10 28
Output
0
499122177
1
748683266
Input
9
4 10 7 1 16 5 9 12 2
Output
0
499122178
2
499122178
798595484
831870296
427819010
Note

In the first example, the answers are: $$$0, \frac{1}{2}, \frac{2}{3}$$$.

In the second example, the answers are: $$$0, \frac{1}{2}, 1, \frac{5}{4}$$$.

In the third example, the answers are: $$$0, \frac{3}{2}, 2, \frac{3}{2}, \frac{8}{5}, \frac{11}{6}, \frac{11}{7}$$$.