F. Say Hello to the Future
time limit per test
1.5 s
memory limit per test
1024 megabytes
input
standard input
output
standard output
"Ugh... Well, can we restart our friendship?"

"What do you mean... You said, restart?"

"..."

A long time ago, Little Cyan Fish prepared a programming contest with his best friend Little $$$\mathcal{F}$$$. They proposed $$$n$$$ problems in total, indexed with the integers from $$$1$$$ to $$$n$$$. The $$$i$$$-th problem ($$$1 \leq i \leq n$$$) has a difficulty rating $$$a_i$$$.

Time flies fast. It has been fifteen months since their contest. Instead of being a participant in the Informatics Olympiad, Little Cyan Fish has transitioned into a coach. But they once had a pact to run a series of championships together.

Little Cyan Fish didn't forget about it.

Now, Little Cyan Fish would like to group these $$$n$$$ problems into several training activities. To ensure the stories in the statements of the tasks are consistent, Little Cyan Fish wants to divide these $$$n$$$ tasks into several intervals. A dividing plan of the problems can be represented by a sequence of integers $$$0 = r_0 \lt r_1 \lt r_2 \lt \cdots \lt r_k = n$$$, meaning that there will be $$$k$$$ training activities, and the $$$i$$$-th training activity will contain all tasks whose indices are between $$$(r_{i - 1} + 1)$$$ and $$$r_i$$$ (both inclusive).

Furthermore, Little Cyan Fish doesn't want an activity to be too unbalanced. If there is a hard problem in an activity, then the activity needs to contain more problems. Formally, if task $$$j$$$ is in the $$$i$$$-th activity (i.e. $$$r_{i - 1} \lt j \leq r_i$$$), then the inequality $$$r_i - r_{i - 1} \geq a_j$$$ must hold.

Little Cyan Fish is interested in how many ways he could divide the problems to satisfy all the requirements above, denoted by $$$f(a)$$$. This question is easy for him, so Little Cyan Fish calculated it easily.

One day before the activities, Little Cyan Fish suddenly realized that those problems were too hard for the participants. Therefore, he came up with a new easy problem with a difficulty rating of only $$$1$$$. He is wondering, for each $$$1 \leq j \leq n$$$, if we define the sequence $$$a^{(j)}$$$ in the following way, what is the value of $$$f(a^{(j)})$$$.

$$$$$$a^{(j)}_i = \begin{cases}1 & i = j \\ a_i & \text{otherwise}\end{cases}$$$$$$

Since the value of $$$f(a^{(j)})$$$ can be extremely large, you only need to output it modulo $$$998\,244\,353$$$.

Input

There is only one test case in each test file.

The first line of the input contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \times 10^5$$$) indicating the number of problems.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$ ($$$1 \leq a_i \leq n$$$), where $$$a_i$$$ is the difficulty rating of the $$$i$$$-th problem.

Output

Output one line contains $$$n$$$ integers separated by a space, where the $$$i$$$-th integer denotes the value of $$$f(a^{(i)})$$$, modulo $$$998\,244\,353$$$.

Please, DO NOT output extra spaces at the end of each line, or your solution may be considered incorrect!

Example
Input
5
1 3 2 1 2
Output
3 6 3 3 6
Note

In the sample test case, for $$$j = 1$$$, we have $$$a^{(j)} = [1, 3, 2, 1, 2]$$$. There are $$$3$$$ ways to assign the problems to the activities, all as follows:

  • $$$[1]$$$, $$$[3, 2, 1, 2]$$$
  • $$$[1, 3, 2]$$$, $$$[1, 2]$$$
  • $$$[1, 3, 2, 1, 2]$$$

For $$$j = 2$$$, we have $$$a^{(j)} = [1, 1, 2, 1, 2]$$$. There are $$$6$$$ ways to assign the problems to the activities, all as follows:

  • $$$[1]$$$, $$$[1]$$$, $$$[2, 1, 2]$$$
  • $$$[1]$$$, $$$[1, 2]$$$, $$$[1, 2]$$$
  • $$$[1]$$$, $$$[1, 2, 1, 2]$$$
  • $$$[1, 1]$$$, $$$[2, 1, 2]$$$
  • $$$[1, 1, 2]$$$, $$$[1, 2]$$$
  • $$$[1, 1, 2, 1, 2]$$$

For $$$j = 3$$$ and $$$j = 4$$$, all the plans are identical to the plans in $$$j = 1$$$.

For $$$j = 5$$$, we have $$$a^{(j)} = [1, 3, 2, 1, 1]$$$. There are $$$6$$$ ways to assign the problems to the activities, all as follows:

  • $$$[1]$$$, $$$[3, 2, 1]$$$, $$$[1]$$$
  • $$$[1]$$$, $$$[3, 2, 1, 1]$$$
  • $$$[1, 3, 2]$$$, $$$[1]$$$, $$$[1]$$$
  • $$$[1, 3, 2]$$$, $$$[1, 1]$$$
  • $$$[1, 3, 2, 1]$$$, $$$[1]$$$
  • $$$[1, 3, 2, 1, 1]$$$