Background

The White King is choosing containers.

Problem Description

The White King made $n$ containers and arranged them in a line, numbered from left to right as $1 \sim n$. The strength of the $i$-th container is $a_i$, and it is guaranteed that all $a_i$ are distinct. To choose the purest container, the White King performs $n - 1$ rounds of operations. In each round, he randomly selects, with equal probability, two containers that are adjacent in position and have not been knocked down, and makes them duel. In a duel, the container with smaller strength will be knocked down and removed from the line.

Obviously, the last remaining container is the one with the greatest strength. However, the poor containers want to know how long they can survive, so they ask you to compute the expected number of rounds each container survives. Output the answers modulo $998244353$.

The number of rounds a container survives is defined as the largest non-negative integer $x < n$ such that it has not been knocked down after round $x$.

Containers $i$ and $j$ are adjacent in position if and only if there does not exist a $k$ such that $i < k < j$ and container $k$ has not been knocked down.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers $a_1, a_2,\cdots,a_n$, with meanings as described above.

Output Format

Output one line with $n$ integers. The $i$-th integer denotes the expected number of rounds that container $i$ survives. To avoid floating-point errors, it is guaranteed that the answer can be represented as an irreducible fraction $\frac{p}{q}$. You only need to output an integer $x (0 \leq x < 998244353)$ such that $qx \equiv p \pmod {998244353}$.

3
3 1 2

2 0 1

3
1 2 3

499122177 499122177 2

5
1 4 2 3 5

499122178 249561091 665496236 582309207 4

Hint

Sample Explanation

In the first sample, the first container can never be knocked down no matter what happens. The second container will surely be knocked down in the first round. The third container will surely not be knocked down in the first round, and will surely be knocked down in the second round.

The real answers for the second sample are $\frac{1}{2}$, $\frac{1}{2}$, $2$.

Constraints

For all test points, it is guaranteed that $1 \leq n \leq 50$, $1 \leq a_i \leq n$, and all $a_i$ are pairwise distinct.

$\text{Subtask 1 (2 pts)}$ $n \leq 2$.

$\text{Subtask 2 (23 pts)}$ $n \leq 6$.

$\text{Subtask 3 (31 pts)}$ $n \leq 18$.

$\text{Subtask 4 (19 pts)}​$ $a_i = i$.

$\text{Subtask 5 (25 pts)}$ No special restrictions.

Hint

If you do not know how to take a fraction modulo a number, you can refer to here.

Translated by ChatGPT 5