408072: GYM102978 J Japanese Knowledge

Memory Limit:1024 MB Time Limit:10 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

J. Japanese Knowledgetime limit per test10 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

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

ExamplesInput
3
1 2 3
Output
5 5 3 1
Input
4
3 3 3 3
Output
15 10 6 3 1
Input
5
10 10 11 11 12
Output
3982 1285 352 77 12 1

加入题单

上一题 下一题 算法标签: