题目描述
杨图由若干行左对齐的单位格组成,各行长度为正整数,并且从上到下不增。记其行长序列为 λ=(λ1,…,λr)。
杨图的共轭是将所有格子的行列坐标交换得到的图形。若共轭的第 j 行长度为 μj,则 μj=∣{i:λi≥j}∣。
对图中的一个格子 (i,j),定义锚定于它的子图为所有满足 x≥i,y≥j 的格子 (x,y)。一次操作可以将这部分子图共轭,再放回同一锚点;其余格子不变。坐标变换为
(x,y)⟼(i+y−j, j+x−i).
只有变换后整个格子集合仍是合法杨图时,操作才允许执行。
定义一个杨图的可爱度为:从它出发,执行任意次(包括零次)合法操作,可以得到的不同杨图的数量。
给定不增的正整数序列 a1,…,an,对于每个 i=1,…,n,求行长为 (a1,…,ai) 的杨图的可爱度,答案对 998244353 取模。
输入格式
第一行为 n,第二行为 n 个整数 a1,…,an。
输出格式
输出 n 个以空格分隔的整数,依次为每个前缀的答案。
数据范围
1≤n≤1000000,n≥a1≥a2≥⋯≥an≥1。本题只有一组数据。
样例输入
3
3 2 1
样例输出
2 3 1
样例说明
(3) 可变为 (3)、(1,1,1);(3,2) 可变为 (3,2)、(3,1,1)、(2,2,1);(3,2,1) 只能得到自身。