C2. Экзамен в БерГУ (усложнённая версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Единственное отличие этой версии от упрощённой — это ограничения.

Если вы пишете на 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$$$ и $$$M$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le M \le 2 \cdot 10^7$$$) — количество студентов и длительность всего экзамена в минутах, соответственно.

Во второй строке входных данных содержится $$$n$$$ целых чисел $$$t_i$$$ ($$$1 \le t_i \le 100$$$) — длительность сдачи экзамена $$$i$$$-го студента.

Гарантируется, что все значения $$$t_i$$$ не превосходят $$$M$$$.

Выходные данные

Выведите $$$n$$$ чисел: $$$i$$$-е число должно быть равно минимальному количеству студентов, которые должны уйти с экзамена, чтобы $$$i$$$-й студент успел ответить (полностью).

Примеры
Входные данные
7 15
1 2 3 4 5 6 7
Выходные данные
0 0 0 0 0 2 3
Входные данные
5 100
80 40 40 40 60
Выходные данные
0 1 1 2 3
Примечание

Пояснение к примеру 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$$$).