统计等差子序列

题目描述

给定长度为 $N$ 的序列 $A = (A_1, A_2, \dots, A_N)$。对于每个 $k = 1, 2, \dots, N$,求 $A$ 的长度为 $k$ 的(不要求连续)等差子序列的数量,结果对 $998244353$ 取模。两个子序列即使作为序列相同,只要取自不同位置即视为不同。

什么是一个子序列? 序列 $A$ 的子序列是指从 $A$ 中删除零个或多个元素后,不改变剩余元素的顺序而得到的序列。

输入格式

输入按以下格式从标准输入给出:

$N$
$A_1$ $A_2$ $\dots$ $A_N$

输出格式

按顺序在一行内以空格分隔输出 $k = 1, 2, \dots, N$ 对应的答案。

样例

5
1 2 3 2 3

5 10 3 0 0

长度为 $1$ 的子序列有 $5$ 个,全部都是等差数列。

长度为 $2$ 的子序列有 $10$ 个,全部都是等差数列。

长度为 $3$ 的等差子序列有 $3$ 个:$(A_1, A_2, A_3)$、$(A_1, A_2, A_5)$、$(A_1, A_4, A_5)$。

长度为 $4$ 及以上的等差子序列不存在。

4
1 2 3 4

4 6 2 1

1
100

1

数据范围

• $1 \le N \le 80$
• $1 \le A_i \le 10^9$
• 所有输入值均为整数。