说明

尼克狐正在计划他的环球旅行！他将造访 $n$ 个不同的地点。每个地点 $i$ 都有一个\textbf{唯一}的"幸福值"，记为 $a_i$，代表尼克在那里感受到的快乐程度。

在规划过程中，尼克对一个组合问题产生了兴趣：对于从 $1$ 到 $n$ 的每个 $k$，幸福值数组中有多少个不同的子序列，其最长递增子序列 (LIS) 的长度恰好等于 $k$？

子序列是指从原始数组中删除零个或多个元素而不改变剩余元素顺序后得到的序列。注意：空子序列（不选择任何地点）也被视为有效子序列，其最长递增子序列的长度为 $0$。

输入格式

第一行包含一个整数 $n (1 \le n \le 35)$，表示地点数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n (1\le a_i\le 10^9)$，表示每个地点的幸福值。

注意，每个 $a_i$ 在整个序列 $\{a\}$ 中都是唯一的。

输出格式

输出 $n+1$ 行，每行包含一个整数。第 $k+1$ 个整数（对于 $k=0 \sim n$）输出 LIS 长度恰好为 $k$ 的子序列的数量。

样例

7
2 5 7 3 10 1 4

1
19
58
42
8
0
0
0