Dueling Containers

There are n containers arranged in a line and numbered from 1 to n (from left to right). The i-th container has a strength of \(a_i\) (all \(a_i\) are distinct). In order to select the purest container, the White King performs \(n-1\) rounds of operations. In each round, he picks uniformly at random one pair of adjacent containers that have not yet been knocked down and makes them duel. In a duel the container with the lower strength is knocked down and removed from the line.

It is clear that in the end only the container with the highest strength survives. However, the containers are curious about how many rounds they can survive. For each container, determine the expected number of rounds it stays standing. For a container, its survival rounds is defined as the largest nonnegative integer \(x < n\) such that it has not been knocked down in round \(x\) (note that all containers are alive before round 0, and if a container is never knocked down then its survival rounds is \(n-1\)).

Two containers are considered adjacent if there is no container between them (in the original order) that has not been knocked down.

The answer for each container is to be given modulo \(998244353\). It is guaranteed that the answer is a rational number which, when computed exactly and reduced modulo \(998244353\), is well–defined.

Note: Although the outcome of every duel is completely determined by the strengths of the two containers, the randomness in the process comes from the order in which duels are chosen.

inputFormat

The input consists of two lines. The first line contains a single integer \(n\) \((2 \le n)\) which is the number of containers. The second line contains \(n\) space–separated integers \(a_1, a_2, \dots, a_n\) representing the strength of each container. All \(a_i\) are distinct.

outputFormat

Output a single line containing \(n\) space–separated integers, where the \(i\)–th integer is the expected number of rounds container \(i\) survives (as defined above) modulo \(998244353\).

sample

2
2 1

1 0