#P18842. [Croatian CPC2021] Idilična ivica
[Croatian CPC2021] Idilična ivica
Idilična ivica
题目描述
Malnar 的花园里有一道由 株植物依次排列组成的篱笆,第 株植物的高度为 ,所有植物的总高度为 。
他打算修剪这些植物。每株植物最多只能被剪一次。修剪时,可以在某个非负整数高度 将一株高于 的植物剪到高度 。但他不太擅长使用剪刀:如果在高度 修剪某株植物,就必须把与它相邻且严格高于 的植物也剪到高度 。被一起修剪的植物同样遵守这一规则。
不必修剪所有植物,也可以完全不修剪。

左图是合法的修剪方式,右图是不合法的修剪方式;右图在第 、 株之间以及第 、 株之间的修剪不符合规则。
对于每个 ,求最终总高度恰好为 的不同篱笆数量。只要至少一株植物的最终高度不同,就认为两道篱笆不同。答案对 取模。
输入格式
第一行包含一个整数 。
第二行包含 个整数 。
输出格式
输出 行。第 行输出总高度为 的不同篱笆数量对 取模后的结果。
数据范围
- ;
- ;
- 。
样例 1
输入
4
0 0 1 6
输出
1
0
1
1
1
1
1
1
样例 2
输入
3
4 6 0
输出
1
0
1
0
1
0
1
0
1
1
1
样例 3
输入
5
1 1 2 1 0
输出
1
0
0
0
1
1
样例 1 解释
无法使总高度为 :如果将第 株剪到高度 ,第 株也必须剪到高度 ;反过来也是如此。
对于 到 中的每个总高度,恰好有一种方式,即只修剪第 株。总高度 对应完全不修剪。将所有植物剪到高度 ,可以得到总高度为 的篱笆。