Say Hello to the Future
“呃……嗯,我们可以重新开始我们的友谊吗?”
“你什么意思……你是说,重新开始?”
“……”
很久以前,小青鱼与他最好的朋友小 F 一起准备了一场程序设计竞赛。他们一共准备了 n 道题目,编号为 1 到 n。第 i 道题目有一个难度评级 ai。
时间过得很快,距离他们举办比赛已经过去了十五个月。小青鱼已经从信息学奥林匹克竞赛选手转型为教练。但他们曾经约定,要一起举办一个系列锦标赛。小青鱼没有忘记这件事。
现在,小青鱼希望把这 n 道题目分为若干场训练活动。为了让题面里的故事背景保持连贯,他要将题目划分为若干个连续区间。一个划分方案可以表示为整数序列
0=r0<r1<⋯<rk=n,
表示共举办 k 场活动,第 i 场活动包含编号 ri−1+1 到 ri 的所有题目,包含两端。
小青鱼也不希望某场活动太不均衡。如果活动中有难题,就应该包含更多题目。形式化地,若题目 j 属于第 i 场活动,即 ri−1<j≤ri,则必须满足
ri−ri−1≥aj.
记满足以上全部要求的划分方案数为 f(a)。这个问题对小青鱼很简单,他轻松地算出了它。
活动开始前一天,小青鱼突然意识到这些题目对参加者来说太难了,于是想出了一道难度评级只有 1 的新题目。他想知道,对于每个 1≤j≤n,将序列定义为
$$a_i^{(j)}=\begin{cases}1,&i=j,\\a_i,&i\ne j,\end{cases}$$
那么 f(a(j)) 是多少。
由于方案数可能很大,只需输出它对 998244353 取模后的结果。
输入格式
每个测试文件只有一组测试数据。
第一行包含整数 n(1≤n≤2×105),表示题目数量。
第二行包含 n 个整数 a1,…,an(1≤ai≤n),其中 ai 是第 i 道题目的难度评级。
输出格式
输出一行 n 个整数,相邻整数用一个空格分隔,第 i 个整数表示 f(a(i))mod998244353。
不要在行末输出多余空格,否则你的答案可能被认为不正确。
原样例
5
1 3 2 1 2
3 6 3 3 6
样例说明
当 j=1 时,a(1)=[1,3,2,1,2],有以下 3 种划分:
- [1], [3,2,1,2]
- [1,3,2], [1,2]
- [1,3,2,1,2]
当 j=2 时,a(2)=[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(5)=[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]