这个问题在某些国家可能广为人知，但如果没人提出，其他国家的人又该如何了解这类问题呢？

给定一个长度为 $N$ 的非递减正整数序列 $A = (A_1, A_2, \dots, A_N)$。

对于每个 $k = 0, 1, 2, \dots, N$，请计算满足以下条件的长度为 $N$ 的非递减非负整数序列 $x = (x_1, x_2, \dots, x_N)$ 的数量，结果对 $998244353$ 取模：

• 对于所有 $1 \le i \le N$，满足 $x_i \le A_i$。
• 满足 $x_i = A_i$ 的下标 $i$ 的个数恰好为 $k$。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 250000$)。

第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$ ($1 \le A_1 \le A_2 \le \dots \le A_N \le 250000$)。

输出格式

对于每个 $k = 0, 1, 2, \dots, N$，输出对应的答案。

样例

样例输入 1

3
1 2 3

样例输出 1

5 5 3 1

样例输入 2

4
3 3 3 3

样例输出 2

15 10 6 3 1

样例输入 3

5
10 10 11 11 12

样例输出 3

3982 1285 352 77 12 1