CF1185C2.Exam in BerSU (hard version)

The only difference between easy and hard versions is constraints.

If you write a solution in Python, then prefer to send it in PyPy to speed up execution time.

A session has begun at Beland State University. Many students are taking exams.

Polygraph Poligrafovich is going to examine a group of $n$ students. Students will take the exam one-by-one in order from $1$-th to $n$-th. Rules of the exam are following:

• The $i$-th student randomly chooses a ticket.
• if this ticket is too hard to the student, he doesn't answer and goes home immediately (this process is so fast that it's considered no time elapses). This student fails the exam.
• if the student finds the ticket easy, he spends exactly $t_i$ minutes to pass the exam. After it, he immediately gets a mark and goes home.

Students take the exam in the fixed order, one-by-one, without any interruption. At any moment of time, Polygraph Poligrafovich takes the answer from one student.

The duration of the whole exam for all students is $M$ minutes ($\max t_i \le M$), so students at the end of the list have a greater possibility to run out of time to pass the exam.

For each student $i$, you should count the minimum possible number of students who need to fail the exam so the $i$-th student has enough time to pass the exam.

For each student $i$, find the answer independently. That is, if when finding the answer for the student $i_1$ some student $j$ should leave, then while finding the answer for $i_2$ ($i_2 \gt i_1$) the student $j$ student does not have to go home.

简单版本与困难版本的唯一区别在于约束条件。

如果你使用 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$ 并不一定需要离场。

The first line of the input contains two integers $n$ and $M$ ($1 \le n \le 2 \cdot 10^5$, $1 \le M \le 2 \cdot 10^7$) — the number of students and the total duration of the exam in minutes, respectively.

The second line of the input contains $n$ integers $t_i$ ($1 \le t_i \le 100$) — time in minutes that $i$-th student spends to answer to a ticket.

It's guaranteed that all values of $t_i$ are not greater than $M$.

输入的第一行包含两个整数 $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$。

Print $n$ numbers: the $i$-th number must be equal to the minimum number of students who have to leave the exam in order to $i$-th student has enough time to pass the exam.

输出 $n$ 个数：其中第 $i$ 个数必须等于为使第 $i$ 个学生有足够时间通过考试而必须离开考场的学生的最少人数。

The explanation for the example 1.

Please note that the sum of the first five exam times does not exceed $M=15$ (the sum is $1+2+3+4+5=15$). Thus, the first five students can pass the exam even if all the students before them also pass the exam. In other words, the first five numbers in the answer are $0$.

In order for the $6$-th student to pass the exam, it is necessary that at least $2$ students must fail it before (for example, the $3$-rd and $4$-th, then the $6$-th will finish its exam in $1+2+5+6=14$ minutes, which does not exceed $M$).

In order for the $7$-th student to pass the exam, it is necessary that at least $3$ students must fail it before (for example, the $2$-nd, $5$-th and $6$-th, then the $7$-th will finish its exam in $1+3+4+7=15$ minutes, which does not exceed $M$).

示例 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$）。