Background

The White King is selecting containers.

Problem Description

The White King has created $n$ containers and arranged them in a queue from left to right, numbered $1$ through $n$. The strength of the $i$-th container is $a_i$, and it is guaranteed that all $a_i$ are distinct. To select the purest container, the White King will perform $n-1$ rounds of operations. In each round, he randomly selects two adjacent and unbeaten containers to duel. In a duel, the container with the lower strength will be defeated and removed from the queue.

Obviously, the container left at the end is the one with the highest strength. However, the poor containers want to know how long they can survive. Therefore, they ask you to calculate the expected number of rounds each container survives. The answer should be taken modulo $998244353$.

The survival rounds of a container is the largest non-negative integer $x < n$ such that it is not defeated in the $x$-th round.

Two containers $i$ and $j$ are adjacent if and only if there is no $k$ such that $i < k < j$ and the $k$-th container is unbeaten.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$, as described in the problem statement.

Output Format

One line with $n$ integers, where the $i$-th integer represents the expected survival rounds of the $i$-th container. To avoid floating-point errors, it is guaranteed that the answer can be expressed as a simplified fraction $\frac{p}{q}$. You only need to output an integer $x$ (where $0 \leq x < 998244353$) such that $\equiv p \pmod{998244353}$.

Sample Input and Output

Sample Input #1

3
3 1 2

Sample Output #1

2 0 1

Sample Input #2

3
1 2 3

Sample Output #2

499122177 499122177 2

Sample Input #3

5
1 4 2 3 5

Sample Output #3

499122178 249561091 665496236 582309207 4

Notes

Sample Explanation

In the first sample, the first container cannot be defeated under any circumstances, the second container will definitely be defeated in the first round, and the third container will definitely survive the first round but be defeated in the second round.

In the second sample, the true answers are $\frac{1}{2}$, $\frac{1}{2}$, and $2$.

Data Range

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

• Subtask 1 (2 pts): $n \leq 2$.
• Subtask 2 (23 pts): $n \leq 6$.
• Subtask 3 (31 pts): $n \leq 18$.
• Subtask 4 (19 pts): $a_i = i$.
• Subtask 5 (25 pts): No additional constraints.

Hints

If you do not know how to take a fraction modulo, you can refer to this link.

见题面 Input 部分

见题面 Output 部分