Problem Description

:::epigraph “Uh... um, can we restart our friendship?”

“What do you mean... you mean, start over?”

“...” :::

A long, long time ago, Xiaoqingyu and his best friend $\mathcal{F}$ prepared a programming contest together. They prepared a total of $n$ problems, numbered with integers from $1$ to $n$. The $i$-th problem ($1 \leq i \leq n$) has a difficulty rating $a_i$.

Time flies. Fifteen months have passed since the contest they held. Xiaoqingyu is no longer an Informatics Olympiad contestant, but has transitioned into a coach. However, they once agreed to hold a series of tournaments together.

And Xiaoqingyu has not forgotten it.

Now, Xiaoqingyu wants to group these $n$ problems into several training sessions. To make sure the story background in the statements is consistent, Xiaoqingyu wants to partition these $n$ problems into several intervals. A partition scheme can be written as an integer sequence $0 = r_0 < r_1 < r_2 < \cdots < r_k = n$, meaning there are $k$ training sessions, where the $i$-th session contains all problems with indices from $(r_{i - 1} + 1)$ to $r_i$ (both ends inclusive).

Besides, Xiaoqingyu does not want any session to be too unbalanced. If a session contains a hard problem, then this session should contain more problems. Formally, if problem $j$ is in the $i$-th session (that is, $r_{i - 1} < j \leq r_i$), then the inequality $r_i - r_{i - 1} \geq a_j$ must hold.

Xiaoqingyu is curious about how many partition schemes can satisfy all the requirements above, and denotes the number by $f(a)$. This problem is very easy for him, so he computed the answer effortlessly.

On the day before these sessions, Xiaoqingyu suddenly realized that these problems were too hard for the contestants. Therefore, he came up with a new easy problem whose difficulty rating is only $1$. He is curious: for each $1 \leq j \leq n$, if we define the sequence $a^{(j)}$ as follows, then 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 very large, you only need to output it modulo $998\,244\,353$.

Input Format

Each test file contains only one set of testdata.

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

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

Output Format

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

Please do not output extra spaces at the end of the line, otherwise your answer may be judged as wrong!

5
1 3 2 1 2

3 6 3 3 6

Hint

In the sample, for $j = 1$, we have $a^{(j)} = [1, 3, 2, 1, 2]$. There are $3$ ways to assign the problems into sessions, 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 into sessions, 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 schemes are the same as those when $j = 1$.

For $j = 5$, we have $a^{(j)} = [1, 3, 2, 1, 1]$. There are $6$ ways to assign the problems into sessions, 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]$

Translated by ChatGPT 5