Description

After staying at home for a long time, you need to find some entertainment. Then you see the following game:

You are given a set with $n$ elements $\{a_1,a_2,a_3....a_n\}$, and all elements are distinct.

The game consists of $n$ rounds in total. In each round, the system randomly picks an element from the set, denoted as $x$. You have two choices:

1. Take $x$, then $x$ will be your final score.
2. Discard $x$. In this case, $x$ will be permanently removed from the set, and the game proceeds to the next round.

Note that if there is only one element left in the set, that element cannot be discarded.

Since you are lazy, you choose a very “slacker” strategy:

For the first $k$ rounds, discard all numbers you get, and record the maximum among them, denoted as $y$.

After round $k$, use the following strategy:

If the obtained $x > y$, take $x$ immediately. Otherwise, keep discarding until you find an $x$ that satisfies the condition, or until only one element remains.

Now you want to know, for each $k$ from $1$ to $n-1$, what your expected score is.

All numbers should be taken modulo $998244353$.

Input Format

The first line contains an integer $n$, the number of elements in the set.

The second line contains $n$ integers, describing each element in the set.

Output Format

Output one line with $n-1$ numbers in total. The $i$-th number represents the expected score when $k=i$.

Let the answer in lowest terms be $\frac{a}{b}$, where $a$ and $b$ are coprime. Output the integer $x$ such that $bx\equiv a \pmod{998244353}$ and $0\leq x < 998244353$. It can be proven that such an integer $x$ is unique.

5
1 2 3 4 5

698771051 399297745 349385527 3

Hint

Sample Explanation

The four numbers that should be output are $\frac{39}{10}, \frac{19}{5} ,\frac{69}{20}, 3$, but under modulo arithmetic, dividing by a number is equivalent to multiplying by its modular inverse, so the output is these values modulo $998244353$. For example, $\frac{39}{10}\equiv 39\cdot 10^{-1}\equiv 39\cdot 299473306\equiv 698771051\pmod{998244353}$.

Hint: If you do not know how to take a fraction modulo a number, click here: https://www.luogu.com.cn/problem/P2613.

• For $40\%$ of the testdata, $2 \leq n \leq 10$.
• For $60\%$ of the testdata, the set is all positive integers in $[1,n]$.
• For $100\%$ of the testdata, $2 \leq n \leq 1000$, and all numbers in the set are at most $10000$.

Translated by ChatGPT 5