Description

有 $n$ 个点，它们从 $1$ 到 $n$ 进行标号，第 $i$ 个点的限制为度数不能超过 $A_i$。

现在对于每个 $s, (1 \leq s \leq n)$ ，问从这 $n$ 个点中选出一些点组成大小为 $s$ 的有标号无根树的方案数。

Input Format

第一行一个整数 $n$。

第二行 $n$ 个整数表示 $A_i$。

Output Format

输出一行 $n$ 个整数，第 $i$ 个整数表示当 $s = i$ 时的方案数。

Sample

样例输入

3
2 2 1

样例输出

3 3 2

Hint

$20 \%$ 的数据，$n \leq 6$

$60 \%$ 的数据，$n \leq 50$

$100 \%$ 的数据，$n \leq 100$