Единственное отличие этой версии от упрощённой — это ограничения.
Если вы пишете на Python, то, наверняка, при отправке вашего решения на PyPy оно будет работать значительно быстрее.
В Берляндском государственном университете началась сессия. Многие студенты уже сдают экзамены.
Совсем скоро Полиграф Полиграфович примет экзамен у группы из \(n\) студентов. Студенты будут сдавать экзамен подряд один за другим в порядке от \(1\)-го до \(n\)-го. Процесс сдачи происходит следующим образом:
- \(i\)-й студент подходит к преподавательскому столу и тянет билет;
- если студент понимает, что билет для него слишком сложный, то он отказывается отвечать и уходит домой (этот процесс происходит настолько быстро, что считается, что на него не расходуется время);
- если студент посчитал, что билет несложный, то он тратит ровно \(t_i\) минут на сдачу экзамена, после чего он получает отметку и уходит домой.
Студенты сдают экзамен один за другим без перерывов. Полиграф Полиграфович в один момент времени принимает экзамен у одного студента.
Длительность всего экзамена составляет \(M\) минут (\(\max t_i \le M\)), поэтому чем ближе студент находится к концу списка, тем больше вероятность того, что он не успеет сдать экзамен.
Ваша задача состоит в том, чтобы для каждого студента \(i\) определить минимальное количество студентов, которые должны уйти домой, чтобы \(i\)-й студент гарантированно успел полностью сдать экзамен.
Для каждого студента \(i\) ответ надо искать независимо, то есть если при нахождении ответа для студента \(i_1\) про какого-то студента \(j\) выяснилость, что он должен уйти, то при нахождении ответа для \(i_2\) (\(i_2>i_1\)) студент \(j\) не обязательно должен уйти домой.
Выходные данные
Выведите \(n\) чисел: \(i\)-е число должно быть равно минимальному количеству студентов, которые должны уйти с экзамена, чтобы \(i\)-й студент успел ответить (полностью).
Примечание
Пояснение к примеру 1.
Обратите внимание, что сумма первых пяти длительностей сдач не превосходит \(M=15\) (сумма равна \(1+2+3+4+5=15\)). Таким образом, первые пять студентов могут сдавать экзамен даже если все студенты до них тоже сдают экзамен. Иными словами, первые пять чисел в ответе равны \(0\).
Для того, чтобы \(6\)-й студент сдал экзамен необходимо, чтобы не менее \(2\)-х студентов до него отказались сдавать (например, \(3\)-й и \(4\)-й, тогда \(6\)-й закончит свою сдачу через \(1+2+5+6=14\) минут, что не превосходит \(M\)).
Для того, чтобы \(7\)-й студент успел сдать экзамен необходимо, чтобы не менее \(3\)-х студентов до него отказались сдавать (например, \(2\)-й, \(5\)-й и \(6\)-й, тогда \(7\)-й закончит свою сдачу через \(1+3+4+7=15\) минут, что не превосходит \(M\)).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 15
1 2 3 4 5 6 7
|
0 0 0 0 0 2 3
|
|
2
|
5 100
80 40 40 40 60
|
0 1 1 2 3
|