2363. [HZOI 2015]COLIS

【题目描述】

输入一个数列$a_{1..n}$，其中$1<=a_{i}<=n$，且任意$a_{i}≠a_{j} (i≠j)$，也就是说$a$是$1~n$的一个排列。

$a$的子序列是从$a$中删除若干个元素后，剩下的元素按照原来顺序组成的序列。显然，$a$有$2^n$个子序列（包括空序列以及$a$本身）。

一个序列$b$的最长上升子序列($LIS$），定义为$b$的最长的满足元素单调递增的子序列。我们用$LIS(b)$来表示$b$的最长上升子序列的长度。

现在，你需要对于$k=0,1,...,n$，求出$a$有多少个子序列$b$，满足$LIS(b)==k$

【输入格式】

第一行一个整数$n (1<=n<=35)$。

第二行是空格隔开的$a_{1},a_{2},...,a_{n}$

【输出格式】

输出$n+1$行，分别为$k=0,1,2,...,n$时的答案

【样例输入】

5
1 5 2 4 3

【样例输出】

1
10
15
6
0
0

【来源】

51Nod