#P18474. Say Hello to the Future

Say Hello to the Future

Say Hello to the Future

“呃……嗯,我们可以重新开始我们的友谊吗?”

“你什么意思……你是说,重新开始?”

“……”

很久以前,小青鱼与他最好的朋友小 F 一起准备了一场程序设计竞赛。他们一共准备了 nn 道题目,编号为 11 到 nn。第 ii 道题目有一个难度评级 aia_i。

时间过得很快,距离他们举办比赛已经过去了十五个月。小青鱼已经从信息学奥林匹克竞赛选手转型为教练。但他们曾经约定,要一起举办一个系列锦标赛。小青鱼没有忘记这件事。

现在,小青鱼希望把这 nn 道题目分为若干场训练活动。为了让题面里的故事背景保持连贯,他要将题目划分为若干个连续区间。一个划分方案可以表示为整数序列

0=r0<r1<⋯<rk=n,0=r_0<r_1<\cdots<r_k=n,

表示共举办 kk 场活动,第 ii 场活动包含编号 ri−1+1r_{i-1}+1 到 rir_i 的所有题目,包含两端。

小青鱼也不希望某场活动太不均衡。如果活动中有难题,就应该包含更多题目。形式化地,若题目 jj 属于第 ii 场活动,即 ri−1<j≤rir_{i-1}<j\le r_i,则必须满足

ri−ri−1≥aj.r_i-r_{i-1}\ge a_j.

记满足以上全部要求的划分方案数为 f(a)f(a)。这个问题对小青鱼很简单,他轻松地算出了它。

活动开始前一天,小青鱼突然意识到这些题目对参加者来说太难了,于是想出了一道难度评级只有 11 的新题目。他想知道,对于每个 1≤j≤n1\le j\le n,将序列定义为

$$a_i^{(j)}=\begin{cases}1,&i=j,\\a_i,&i\ne j,\end{cases}$$

那么 f(a(j))f(a^{(j)}) 是多少。

由于方案数可能很大,只需输出它对 998 244 353998\,244\,353 取模后的结果。

输入格式

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

第一行包含整数 nn(1≤n≤2×1051\le n\le2\times10^5),表示题目数量。

第二行包含 nn 个整数 a1,…,ana_1,\ldots,a_n(1≤ai≤n1\le a_i\le n),其中 aia_i 是第 ii 道题目的难度评级。

输出格式

输出一行 nn 个整数,相邻整数用一个空格分隔,第 ii 个整数表示 f(a(i)) mod 998 244 353f(a^{(i)})\bmod998\,244\,353。

不要在行末输出多余空格,否则你的答案可能被认为不正确。

原样例

5
1 3 2 1 2
3 6 3 3 6

样例说明

当 j=1j=1 时,a(1)=[1,3,2,1,2]a^{(1)}=[1,3,2,1,2],有以下 33 种划分:

  • [1], [3,2,1,2][1],\ [3,2,1,2]
  • [1,3,2], [1,2][1,3,2],\ [1,2]
  • [1,3,2,1,2][1,3,2,1,2]

当 j=2j=2 时,a(2)=[1,1,2,1,2]a^{(2)}=[1,1,2,1,2],有以下 66 种划分:

  • [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]
  • [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=3j=3 或 j=4j=4 时,合法划分与 j=1j=1 时完全相同。

当 j=5j=5 时,a(5)=[1,3,2,1,1]a^{(5)}=[1,3,2,1,1],有以下 66 种划分:

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