题目描述

:::epigraph “呃…嗯，我们可以重新开始我们的友谊吗？”

“你什么意思…你是说，重新开始？”

“…” :::

很久很久以前，小青鱼与他最好的朋友小 $\mathcal{F}$ 一起准备了一场程序设计竞赛。他们准备一共了 $n$ 道题目，编号为从 $1$ 到 $n$ 的整数。第 $i$ 道题目（$1 \leq i \leq n$）有一个难度评级 $a_i$。

时间过得很快。距离他们举办的比赛已经过去十五个月了。小青鱼已经不再是 Informatics Olympiad 的选手了，而是转型成为了一名教练。但他们曾有过约定，要一起举办一组系列锦标赛。

而小青鱼没有忘掉它。

现在，小青鱼想要把这 $n$ 道题目分组为若干场训练活动。为了确保题目的题面中包含的故事背景一致，小青鱼想要把这 $n$ 道题目划分成若干个区间。一个划分题目的方案可以记为一个整数序列 $0 = r_0 < r_1 < r_2 < \cdots < r_k = n$，表示共有 $k$ 场训练活动，其中第 $i$ 场活动包含所有编号在 $(r_{i - 1} + 1)$ 和 $r_i$ 之间（含两端）的题目。

除此以外，小青鱼不想让某一场活动变得太不平衡。如果一场活动中包含一道困难的题目，那么这个活动就应该包含更多的题目。形式化地，如果题目 $j$ 在第 $i$ 个活动中（也就是说，$r_{i - 1} < j \leq r_i$），那么不等式 $r_i - r_{i - 1} \geq a_j$ 必须成立。

小青鱼很好奇能够有多少种划分题目的方案可以满足上述所有要求，并把方案数记做 $f(a)$。这个问题对他来说很简单，所以小青鱼很轻松地就算出了答案。

在这些活动的前一天，小青鱼突然意识到这些题目对选手来说太困难了。因此，他想到了一道新的简单题目，其难度评级只有 $1$。他很好奇，对每个 $1 \leq j \leq n$，如果我们使用如下方式定义序列 $a^{(j)}$，那么 $f(a^{(j)})$ 的值是多少。

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

因为 $f(a^{(j)})$ 的值可以非常大，您只需要输出它对 $998\,244\,353$ 取模后的结果。

输入格式

每个测试文件仅有一组测试数据。

第一行输入一个整数 $n$ （$1 \leq n \leq 2 \times 10^5$）表示题目的数量。

第二行输入 $n$ 个整数 $a_1, a_2, \cdots, a_n$ （$1 \leq a_i \leq n$），其中 $a_i$ 表示第 $i$ 道题目的难度评级。

输出格式

输出一行 $n$ 个由单个空格分隔的整数，其中第 $i$ 个整数表示 $f(a^{(i)})$ 的值对 $998\,244\,353$ 取模后的结果。

请不要在行末输出多余空格，否则您的答案可能会被认为是错误的！

5
1 3 2 1 2

3 6 3 3 6

提示

在样例数据中，对于 $j = 1$，我们有 $a^{(j)} = [1, 3, 2, 1, 2]$。有 $3$ 种方法将题目分配到活动中，如下所示：

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

对于 $j = 2$，我们有 $a^{(j)} = [1, 1, 2, 1, 2]$。有 $6$ 种方法将题目分配到活动中，如下所示：

• $[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]$

对于 $j = 3$ 和 $j = 4$，所有的方案与 $j = 1$ 时的方案相同。

对于 $j = 5$，我们有 $a^{(j)} = [1, 3, 2, 1, 1]$。有 $6$ 种方法将题目分配到活动中，如下所示：

• $[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]$