解题思路

设数组为 $a_1,\dots,a_n$，对每个 $k(1\le k\le n)$ 要求所有长度为 $k$ 的子序列 $b$ 的最大值 $f(b)=\max(b)$ 之和，答案对 $998244353$ 取模。

关键观察（计数法） 将数组按非降序排序，记为 $A_1\le A_2\le \cdots\le A_n$。把每个长度为 $k$ 的子序列唯一地“归属”给其最大值在原序中的最右位置 $i$。 当最大值归属在位置 $i$ 时，其余 $k-1$ 个元素只能从 $[1,\,i-1]$ 中任取（都不超过 $A_i$），共有

题目内容

Zeeman 有一个长度为 $1≦n≦5*10^3$ 的正整数数组 $a$ 。

定义 $f(b)=max(b_1,b_2,...,b_m)$ 。Zeeman 想知道，对于任意的 $1≦k≦ n$ ，数组 $a$ 中所有长度为 $k$ 的子序列 $b$ 的 $f(b)$之和。

由于答案可能很大，请将答案对 $998244353$ 取模后输出：

子序列：子序列为从原数组中删除任意个(可以为零或全部)数字得到的新数组，数字的相对顺序保持不变。例如，数组 {$1,2,3$} 的子序列包括 {}、{$1$}、{$2$}、{$3$}、{$1,2$}、{$1,3$}、{$2,3$} 与 {$1,2,3$} 。

输入描述

第一行输入一个正整数 $1≦ n≦5*10^3$ ，表示数组长度。

第一行输入 $n$ 个正整数，表示数组 $a$，其中 $\forall 1 ≦i≦n,1 ≦ a_i ≦ 10^9$。

输出描述

输出一行 $n$ 个整数，其中第 $1 ≦ k ≦ n$ 个整数表示所有长度为 $k$ 的子序列 $b$ 的 $f(b)$ 之和对 $998244353$ 取模后的结果。

样例1

输入

5
1 2 3 4 5

输出

15 40 45 24 5