#B. 合唱队形

    传统题 1000ms 512MiB

合唱队形

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

合唱队有nn个成员,他们的身高参差不齐。想要站在学校的大舞台上演出,首先必须要排出一个看得顺眼的队形。我们称满足下面这样的队形是整齐的:

对于kk个人排成的队伍,第ii个人的身高为hih_i,存在一个1ik1\le i\le k,使得当j<ij<i时,hj<hj+1h_j<h_{j+1},当j>ij>i时,hj<hj1h_j<h_{j-1}

合唱队的负责人还说,并不一定所有人都要在最终的队形中

小W认为仅仅排出一个队形还是比较简单的,因此他在思考一个进一步的问题:

在最终队形中的人数分别11~nn时,分别有多少种排列方案使得队形是整齐的。两种排列方案不同当且仅当存在某个位置上的成员编号不同。

然而小W实在太菜了,无法得到这个问题的答案,于是小W把问题交给了你。

Format

Input

第一行输入一个整数nn,表示合唱队成员的数目。

接下来一行,输入nn个整数,其中第ii个整数表示编号为ii的成员的身高hih_i

Output

输出nn行,每行输出一个整数,第ii行输出当最终队形中人数为ii时的合法方案数目。

因为答案可能很大,所以请你将其对109+710^9+7取模后输出。

Samples

3
1 2 1
3
4
2

Limitation

【样例解释】

合法的排列方案有:1,2,3,12,21,23,32,123,3211,2,3,12,21,23,32,123,321

其中每个数字串代表一种排列方案,数字串中的每个数字代表对应位置队员的编号。

【数据范围】

对于30%30\%的数据:1n,hi101\le n,h_i\le 10

对于60%60\%的数据:1n,hi2001\le n,h_i\le 200

对于100%100\%的数据:1n,hi20001\le n,h_i\le 2000

9-17测试

未参加
状态
已结束
规则
OI
题目
4
开始于
2022-9-17 8:00
结束于
2022-9-17 12:30
持续时间
4.5 小时
主持人
参赛人数
20