Japanese Knowledge

Time limit10sMemory limit512 MB

Summary

For each k from 0 to N, count non-decreasing sequences x with x_i at most A_i in which exactly k positions have x_i equal to A_i, modulo 998244353.

Level: Hard9 of 10
Topics: Dynamic programming, Divide and conquer, Combinatorics, Math
Solved: No attempts yet

Problem

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 the 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$ .

Input

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$ ).

Output

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

Examples3

Example 1
Input
```
3
1 2 3
```
Expected output
```
5 5 3 1
```
Example 2
Input
```
4
3 3 3 3
```
Expected output
```
15 10 6 3 1
```
Example 3
Input
```
5
10 10 11 11 12
```
Expected output
```
3982 1285 352 77 12 1
```