简单版本和困难版本之间的唯一区别是限制。
贝兰州立大学的会议已开始。许多学生正在参加考试。
测谎仪 Poligrafovich 将对一组 $$$n$$$ 学生进行检查。学生将按照从 $$$1$$$-th 到 $$$n$$$-th 的顺序逐一参加考试。考试规则如下:
- 第 $$$i$$$ 学生随机选择一张票。
- 如果这张票对学生来说太难了,他不会回答并立即回家(这个过程非常快,以至于被认为没有时间流逝)。这个学生考试不及格。
- 如果学生发现考试很容易,他就会花费 $$$t_i$$$ 分钟通过考试。之后,他立即获得分数并回家。
学生按照固定顺序,逐一参加考试,不得中断。波利格拉福维奇随时都会从一名学生那里得到答案。
所有学生的整个考试持续时间为 $$$M$$$ 分钟 ($$$\max t_i \le M$$$),因此列表末尾的学生更有可能没有时间通过考试。
对于每个学生 $$$i$$$,您应该计算需要通过考试的最少可能学生人数,以便第 $$$i$$$ 个学生有足够的时间通过考试。
对于每个学生 $$$i$$$,独立找到答案。也就是说,如果在为学生 $$$i_1$$$ 寻找答案时,某个学生 $$$j$$$ 应该离开,那么在为 $$$i_2$$$ ($$$i_2>i_1$$$) 寻找答案时,学生 $$$j$$$ 不必回家。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$M$$$ ($$$1 \le n \le 100$$$, $$$1 \le M \le 100$$$) - 分别是学生人数和考试总持续时间(以分钟为单位)。
输入的第二行包含 $$$n$$$ 整数 $$$t_i$$$ ($$$1 \le t_i \le 100$$$) - 第 $$$i$$$ 学生回答问题所花费的时间(以分钟为单位)。
保证 $$$t_i$$$ 的所有值不大于 $$$M$$$。
输出
打印$$$n$$$数字:第$$$i$$$个数字必须等于必须离开考试的学生的最少人数,以便第$$$i$$$个学生有足够的时间通过考试。
示例
输入 #1
7 15 1 2 3 4 5 6 7
输出 #1
0 0 0 0 0 2 3
输入 #2
5 100 80 40 40 40 60
输出 #2
0 1 1 2 3
注意
示例1的解释。
请注意,前五次考试时间总和不超过$$$M=15$$$(总和为$$$1+2+3+4+5=15$$$)。因此,即使前面的所有学生都通过了考试,前五名学生也可以通过考试。换句话说,答案中的前五个数字是$$$0$$$。
为了让第 $$$6$$$-th 学生通过考试,必须至少有 $$$2$$$ 学生之前未通过考试(例如,$$$3$$$-rd 和 $$$4$$$-th,那么第 $$$6$$$-th 将在 $$$1+2+5+6=14$$$ 分钟内完成考试,时间不超过$$$M$$$)。
为了让第 $$$7$$$-th 学生通过考试,必须有至少 $$$3$$$ 学生之前未通过考试(例如,$$$2$$$-nd、$$$5$$$-th 和 $$$6$$$-th,那么第 $$$7$$$-th 将在 $$$1+3+4+7=15$$$ 分钟内完成考试,不超过 $$$M$$$)。