시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 512 MB 3 2 2 66.667%

문제

This problem might be well-known in some countries, but how do other countries learn about such problems if nobody poses them?

You are given a non-decreasing positive integer sequence $A = (A_1, A_2, \ldots, A_N)$ of length $N$. For each $k=0,1,2,\ldots,N$, count the number of non-decreasing non-negative integer sequences $x = (x_1, x_2, \ldots, x_N)$ of length $N$ that satisfy following conditions, modulo $998244353$:

  • $x_i \leq A_i$ for all $1 \leq i \leq N$.
  • The number of indices $i$ with $x_i=A_i$ is exactly $k$.

입력

The first line contains an integer $N$ ($1 \leq N \leq 250000$).

The second line contains $N$ integers $A_1,A_2,\ldots,A_N$ ($1 \leq A_1 \leq A_2 \leq \cdots \leq A_N \leq 250000$).

출력

For each $k=0,1,2,\ldots,N$, print the answer.

예제 입력 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