P6046 Pure Containers

The White King is choosing containers.

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.

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 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}$.

#### 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](https://www.luogu.com.cn/problem/P3811). Translated by ChatGPT 5