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>i_1$) the student $j$ student does not have to go home.


-----Input-----

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$.


-----Output-----

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.


-----Examples-----
Input
7 15
1 2 3 4 5 6 7

Output
0 0 0 0 0 2 3 
Input
5 100
80 40 40 40 60

Output
0 1 1 2 3 


-----Note-----

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$).

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Complete search

Data structures

Mathematics

Greedy algorithms


Solutions:
import sys, math

def read_int():
	return int(sys.stdin.readline().strip())

def read_int_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def read_string():
	return sys.stdin.readline().strip()

def read_string_list(delim=' '):
	return sys.stdin.readline().strip().split(delim)

def print_list(l):
	print(' '.join(map(str, l)))
import heapq

def compute(diff_wanted, freqs):
	out = 0
	for i in range(99, -1, -1):
		if diff_wanted <= 0:
			break
		if freqs[i] * (i + 1) <= diff_wanted:
			diff_wanted -= freqs[i] * (i + 1)
			out += freqs[i]
		else:
			consumption = min(freqs[i], math.ceil(diff_wanted / (i + 1)))
			diff_wanted -= consumption * (i + 1)
			out += consumption
	return out
(n, m) = read_int_list()
times = read_int_list()
sum_array = [0 for _ in range(n)]
sum_array[0] = times[0]
for i in range(1, n):
	sum_array[i] = sum_array[i - 1] + times[i]
freqs = [0 for _ in range(100)]
for i in range(n):
	if sum_array[i] > m:
		ans = compute(sum_array[i] - m, freqs)
		print(ans, end=' ')
	else:
		print('0', end=' ')
	freqs[times[i] - 1] += 1
print()


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
a = [0 for i in range(101)]
ans = []
for i in range(n):
	if i == 0:
		a[l[i]] += 1
		ans.append(0)
	else:
		s = 0
		t = m - l[i]
		count = 0
		for j in range(1, 101):
			if a[j] * j < t - s:
				s += a[j] * j
				count += a[j]
			else:
				u = (t - s) // j
				ans.append(i - count - u)
				break
		else:
			ans.append(0)
		a[l[i]] += 1
for i in ans:
	print(i, end=' ')


(n, m) = list(map(int, input().split()))
if n == 1:
	print(0)
	exit(0)
t = list(map(int, input().split()))
dp = [0] * 101
ans = []
for i in range(len(t)):
	s = 0
	lim = m - t[i]
	f = False
	c = 0
	for j in range(1, 101):
		if f:
			c += dp[j]
			continue
		if dp[j]:
			if s + dp[j] * j > lim:
				c += dp[j] - (lim - s) // j
				f = True
			s += dp[j] * j
	dp[t[i]] += 1
	ans.append(c)
print(*ans)


import sys
input = sys.stdin.readline

def main():
	(N, M) = map(int, input().split())
	A = list(map(int, input().split()))
	T = [0] * 101
	s = 0
	ans = []
	for a in A:
		s += a
		ss = max(s - M, 0)
		count = 0
		for t in range(100, 0, -1):
			c = T[t]
			if ss - t * c > 0:
				count += c
				ss -= t * c
			else:
				count += ss // t
				if ss % t != 0:
					count += 1
				break
		T[a] += 1
		ans.append(count)
	for a in ans:
		print(a, end=' ')
	print()
main()


(n, m) = map(int, input().split())
l = [int(i) for i in input().split()]
from math import ceil
from collections import defaultdict
freq = defaultdict(int)
sm = 0
for i in range(n):
	sm += l[i]
	cnt = 0
	if sm <= m:
		print(0, end=' ')
	else:
		rem = sm - m
		curr = 0
		cnt = 0
		for x in range(100, 0, -1):
			f = freq[x]
			if curr + f * x <= rem:
				curr += f * x
				cnt += f
			else:
				now = rem - curr
				cnt += ceil(now / x)
				curr = rem
				break
		print(cnt, end=' ')
	freq[l[i]] += 1


(n, m) = list(map(int, input().split()))
t = list(map(int, input().split()))
freq = []
for i in range(101):
	freq.append(0)
for i in range(0, n):
	time = m - t[i]
	num = 0
	for j in range(1, 101):
		p = int(time / j)
		if p >= freq[j]:
			time -= freq[j] * j
			num += freq[j]
		else:
			time -= p * j
			num += p
	print(i - num, end=' ')
	freq[t[i]] += 1


(a, b) = map(int, input().split())
z1 = [0] * 101
z = list(map(int, input().split()))
for i in range(a):
	s = z[i]
	p = 0
	for j in range(1, 101):
		k = j * z1[j]
		if s + k <= b:
			s += k
		else:
			f = b - s
			p = sum(z1[j + 1:]) + z1[j] - f // j
			break
	z1[z[i]] += 1
	print(p, end=' ')


import math
nM = input().split(' ')
n = int(nM[0])
M = int(nM[1])
a = list(map(int, input().split(' ')))
carr = [0 for i in range(100)]
carr[a[0] - 1] += 1
print('0', end=' ')
sum = a[0]
for i in range(1, len(a)):
	failed = 0
	if sum + a[i] > M:
		A = sum + a[i]
		for itr in range(100, 0, -1):
			if A - carr[itr - 1] * itr > M:
				A -= carr[itr - 1] * itr
				failed += carr[itr - 1]
			else:
				failed += math.ceil((A - M) / itr)
				break
		print(failed, end=' ')
	else:
		print(failed, end=' ')
	sum += a[i]
	carr[a[i] - 1] += 1


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def main():
	import math
	(n, m) = map(int, input().split())
	vals = list(map(int, input().split()))
	time = [0 for s in range(100)]
	ans = [0 for s in range(n)]
	count = 0
	for s in range(n):
		if vals[s] > m - count:
			people = 0
			cur = m - count
			ind = 99
			while vals[s] > cur and ind >= 0:
				if vals[s] <= cur + time[ind] * (ind + 1):
					diff = math.ceil((vals[s] - cur) / (ind + 1))
					people += diff
					cur += diff * (ind + 1)
				else:
					cur += time[ind] * (ind + 1)
					people += time[ind]
				ind -= 1
			ans[s] = people
		count += vals[s]
		time[vals[s] - 1] += 1
	print(*ans)
main()


import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

def read_int():
	return int(input())

def read_int_n():
	return list(map(int, input().strip().split()))

def read_float():
	return float(input())

def read_float_n():
	return list(map(float, input().split()))

def read_str():
	return input().strip()

def read_str_n():
	return list(map(str, input().split()))

def error_print(*args):
	print(*args, file=sys.stderr)

def mt(f):
	import time

	def wrap(*args, **kwargs):
		s = time.time()
		ret = f(*args, **kwargs)
		e = time.time()
		error_print(e - s, 'sec')
		return ret
	return wrap

def slv(N, M, S):
	ans = []
	m = 0
	c = [0] * (max(S) + 1)
	for (i, s) in enumerate(S):
		sm = 0
		sp = 0
		m = M - s
		for j in range(1, len(c)):
			if m < sm + c[j] * j:
				sp += (m - sm) // j
				break
			else:
				sm += c[j] * j
				sp += c[j]
		ans.append(i - sp)
		c[s] += 1
	return ' '.join(map(str, ans))

def main():
	(N, M) = read_int_n()
	S = read_int_n()
	print(slv(N, M, S))
main()


arr = list(map(int, input().split()))
(n, m) = (arr[0], arr[1])
s = str(input())
a = [int(i) for i in s.split()]
answers = []
s = 0
count = 0
max_val = 0
k = 0
arr = [0 for i in range(101)]
for elem in a:
	if s + elem > m:
		i = max_val
		s2 = s
		c2 = count
		while s2 + elem > m:
			if s2 - arr[i] * i + elem <= m:
				ans = k - c2 + (arr[i] - (m - elem - (s2 - arr[i] * i)) // i)
				s2 -= i * (arr[i] - (m - elem - (s2 - arr[i] * i)) // i)
			else:
				s2 -= arr[i] * i
				c2 -= arr[i]
				i -= 1
		if elem < max_val:
			arr[elem] += 1
			arr[max_val] -= 1
			s = s - max_val + elem
			j = max_val
			while arr[j] < 1:
				j -= 1
			max_val = j
	else:
		arr[elem] += 1
		s += elem
		ans = k - count
		count += 1
		if elem > max_val:
			max_val = elem
	answers.append(str(ans))
	k += 1
print(' '.join(answers))


(n, M) = list(map(int, input().split()))
nums = list(map(int, input().split()))
count = [0] * 101
tm = 0
for i in range(n):
	ans = 0
	tm += nums[i]
	if tm > M:
		extra = tm - M
		itr = 100
		while extra > 0:
			extra -= itr * count[itr]
			ans += count[itr]
			itr -= 1
		ans -= -extra // (itr + 1)
	print(ans)
	count[nums[i]] += 1


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
import bisect
from heapq import *
from math import *
from collections import deque
from collections import Counter as counter
from itertools import combinations as comb
from itertools import permutations as permutate
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def graph(vertex):
	return [[] for i in range(0, vertex + 1)]

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(a, b):
	ans = 1
	while b > 0:
		if b % 2 == 1:
			ans *= a
		a *= a
		b //= 2
	return ans

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def bs(a, l, h, x):
	while l < h:
		mid = (l + h) // 2
		if a[mid] == x:
			return mid
		if a[mid] < x:
			l = mid + 1
		else:
			h = mid
	return l

def sieve(a):
	for i in range(3, 10 ** 6 + 1, 2):
		a[i] = 1
	for i in range(3, 10 ** 6 + 1, 2):
		for j in range(i * i, 10 ** 6 + 1, i):
			a[j] = 0
	a[2] = 1
	return a

def bfs(g, st):
	visited = [0] * len(g)
	visited[st] = 1
	queue = []
	queue.append(st)
	new = []
	while len(queue) != 0:
		s = queue.pop()
		new.append(s)
		for i in g[s]:
			if visited[i] == 0:
				visited[i] = 1
				queue.append(i)
	return new

def solve():
	(n, m) = sep()
	a = lis()
	cnt = [0] * 101
	ans = []
	for i in range(0, n):
		if i == 0:
			ans.append(0)
			cnt[a[i]] += 1
			continue
		rem = m - a[i]
		curr = 0
		count = 0
		for j in range(1, 101):
			if curr + cnt[j] * j <= rem:
				count += cnt[j]
				curr += cnt[j] * j
				continue
			else:
				count += (rem - curr) // j
				break
		ans.append(i - count)
		cnt[a[i]] += 1
	print(*ans)
testcase(1)


import sys
input = sys.stdin.readline
(n, M) = list(map(int, input().split()))
t = list(map(int, input().split()))
ans = []
tmp = [0] * 101
for i in range(n):
	num = 0
	T = t[i]
	for j in range(1, 101):
		if T + j * tmp[j] <= M:
			num += tmp[j]
			T += j * tmp[j]
		else:
			m = M - T
			num += m // j
			break
	ans.append(i - num)
	tmp[t[i]] += 1
print(*ans)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
cnt = [0] * 101
curr = 0
for i in range(n):
	tm = m - a[i]
	ans = 0
	for j in range(1, 101):
		tmp = int(tm / j)
		if tmp >= cnt[j]:
			tm -= cnt[j] * j
			ans += cnt[j]
		else:
			tm -= tmp * j
			ans += tmp
	print(i - ans, end=' ')
	cnt[a[i]] += 1


import math
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = [a[0]]
for i in a[1:]:
	b.append(b[-1] + i)
ans = [0]
c = [0] * 101
c[a[0]] = 1
for i in range(1, n):
	s = b[i]
	j = 100
	an = 0
	while s > m:
		if s - j * c[j] >= m:
			s -= j * c[j]
			an += c[j]
		else:
			an += math.ceil((s - m) / j)
			s = m
		j -= 1
	c[a[i]] += 1
	ans.append(an)
print(*ans)


(n, t) = map(int, input().split())
arr = list(map(int, input().split()))
v = 0
ans = [0] * 101
for i in range(n):
	cnt = 0
	v += arr[i]
	extra = v - t
	k = 100
	while extra > 0 and k > 0:
		if ans[k] * k >= extra:
			cnt += (extra + k - 1) // k
			break
		elif ans[k] * k < extra:
			extra -= ans[k] * k
			cnt += ans[k]
		k -= 1
	ans[arr[i]] += 1
	print(cnt, end=' ')


import os
import heapq
import sys, threading
import math
import bisect
import operator
from collections import defaultdict
sys.setrecursionlimit(10 ** 5)
from io import BytesIO, IOBase

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

def power(x, p, m):
	res = 1
	while p:
		if p & 1:
			res = res * x % m
		x = x * x % m
		p >>= 1
	return res

def inar():
	return [int(k) for k in input().split()]

def lcm(num1, num2):
	return num1 * num2 // gcd(num1, num2)

def main():
	t = 1
	for _ in range(t):
		(n, m) = inar()
		arr = inar()
		freq = [0] * 101
		sm = 0
		for i in range(n):
			take = sm + arr[i] - m
			k = 0
			if take > 0:
				for j in range(100, 0, -1):
					value = j * freq[j]
					if value > take:
						k += (take + j - 1) // j
						break
					k += freq[j]
					take -= value
			sm += arr[i]
			freq[arr[i]] += 1
			print(k, end=' ')
		print()
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import math
(a, b) = map(int, input().split())
c = list(map(int, input().split()))
j = [0] * 101
m = 0
for x in range(a):
	m += c[x]
	if m <= b:
		print(0, end=' ')
		j[100 - c[x]] += 1
	else:
		l = 0
		f = m - b
		for y in range(101):
			if j[y] != 0:
				if f <= (100 - y) * j[y]:
					if f < 100 - y:
						l += 1
						print(l, end=' ')
						break
					else:
						l += math.ceil(f / (100 - y))
						print(l, end=' ')
						break
				else:
					l += j[y]
					f -= j[y] * (100 - y)
		j[100 - c[x]] += 1


def main1():
	buf = input()
	buflist = buf.split()
	n = int(buflist[0])
	M = int(buflist[1])
	buf = input()
	buflist = buf.split()
	t = list(map(int, buflist))
	student = []
	minimum = []
	for i in range(n):
		count = 0
		pointer = 0
		while pointer < i:
			if count + student[pointer] <= M - t[i]:
				count += student[pointer]
				pointer += 1
			else:
				break
		minimum.append(i - pointer)
		student.append(t[i])
		student.sort()
	print(' '.join(list(map(str, minimum))))

def main2():
	buf = input()
	buflist = buf.split()
	n = int(buflist[0])
	M = int(buflist[1])
	buf = input()
	buflist = buf.split()
	t = list(map(int, buflist))
	bucket = []
	for i in range(101):
		bucket.append(0)
	minimum = []
	for i in range(n):
		target = M - t[i]
		count = 0
		subtotal = 0
		for j in range(1, 101):
			if subtotal + bucket[j] * j > target:
				count += (target - subtotal) // j
				break
			else:
				count += bucket[j]
				subtotal += bucket[j] * j
		minimum.append(i - count)
		bucket[t[i]] += 1
	print(' '.join(list(map(str, minimum))))

def __starting_point():
	main2()
__starting_point()


def naiveSolve():
	return

def main():
	(n, M) = readIntArr()
	t = readIntArr()
	tCnts = [0] * 101
	ans = [-1] * n
	for i in range(n):
		total = t[i]
		for j in range(1, 101):
			total += j * tCnts[j]
		if total <= M:
			ans[i] = 0
		else:
			removalCnts = 0
			for j in range(100, 0, -1):
				subtractable = tCnts[j]
				x = (total - M + j - 1) // j
				x = min(x, subtractable)
				removalCnts += x
				total -= j * x
				if total <= M:
					break
			ans[i] = removalCnts
		tCnts[t[i]] += 1
	oneLineArrayPrint(ans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(l, r):
	print('? {} {}'.format(l, r))
	sys.stdout.flush()
	return int(input())

def answerInteractive(x):
	print('! {}'.format(x))
	sys.stdout.flush()
inf = float('inf')
MOD = 998244353
from math import gcd, floor, ceil
for _abc in range(1):
	main()


import sys
from heapq import *
heap = []
heapify(heap)
for _ in range(1):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	ans = [0] * n
	(a, b) = (0, 0)
	for i in range(n):
		temp = []
		while a + l[i] > k:
			temp.append(heappop(heap))
			a += temp[-1]
		ans[i] = len(temp) + b
		while temp:
			a -= temp[-1]
			heappush(heap, temp.pop())
		a += l[i]
		heappush(heap, -l[i])
		if a > k:
			a += heappop(heap)
			b += 1
	print(*ans)


(n, M) = map(int, input().split())
t = list(map(int, input().split()))
f = [0 for _ in range(101)]
a = []
for i in range(n):
	Mi = M - t[i]
	c = 0
	for j in range(1, 101):
		k = min(Mi // j, f[j])
		Mi -= k * j
		c += k
	a.append(i - c)
	f[t[i]] += 1
print(' '.join(map(str, a)))


(n, m) = map(int, input().strip().split())
arr = list(map(int, input().strip().split()))
cnt = [0] * 101
curr = 0
for i in range(n):
	res = 0
	val = curr + arr[i] - m
	t = 100
	while t > 0 and val > 0:
		d = min(cnt[t], (val + t - 1) // t)
		res += d
		val -= d * t
		t -= 1
	print(res, end=' ')
	curr += arr[i]
	cnt[arr[i]] += 1


from sys import stdin, stdout, maxsize as mxs
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
from typing import Counter
from itertools import accumulate
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def iinp():
	return int(inp())

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def smp():
	return map(str, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(m, val) for j in range(n)]

def remadd(x, y):
	return 1 if x % y else 0

def ceil(a, b):
	return (a + b - 1) // b

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True
(n, k) = mp()
arr = lmp()
cnt = l2d(n + 1, 101)
for i in range(1, n + 1):
	for j in range(1, 101):
		if j == arr[i - 1]:
			cnt[i][j] = cnt[i - 1][j] + 1
		else:
			cnt[i][j] = cnt[i - 1][j]
ansl = []
s = 0
for i in range(n):
	s += arr[i]
	c = 0
	if s > k:
		df = s - k
		for j in range(100, 0, -1):
			x = min(cnt[i][j], ceil(df, j))
			df -= j * x
			c += x
			if df <= 0:
				break
	ansl.append(c)
print(*ansl)


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest
INF = 999999999999999999999999
alphabets = 'abcdefghijklmnopqrstuvwxyz'

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

class SegTree:

	def __init__(self, n):
		self.N = 1 << n.bit_length()
		self.tree = [0] * (self.N << 1)

	def update(self, i, j, v):
		i += self.N
		j += self.N
		while i <= j:
			if i % 2 == 1:
				self.tree[i] += v
			if j % 2 == 0:
				self.tree[j] += v
			(i, j) = (i + 1 >> 1, j - 1 >> 1)

	def query(self, i):
		v = 0
		i += self.N
		while i > 0:
			v += self.tree[i]
			i >>= 1
		return v

def SieveOfEratosthenes(limit):
	isPrime = [True] * (limit + 1)
	isPrime[0] = isPrime[1] = False
	primes = []
	for i in range(2, limit + 1):
		if not isPrime[i]:
			continue
		primes += [i]
		for j in range(i * i, limit + 1, i):
			isPrime[j] = False
	return primes
from collections import Counter

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def memodict(f):

	class memodict(dict):

		def __missing__(self, key):
			ret = self[key] = f(key)
			return ret
	return memodict().__getitem__

def pollard_rho(n):
	if n & 1 == 0:
		return 2
	if n % 3 == 0:
		return 3
	s = (n - 1 & 1 - n).bit_length() - 1
	d = n >> s
	for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
		p = pow(a, d, n)
		if p == 1 or p == n - 1 or a % n == 0:
			continue
		for _ in range(s):
			prev = p
			p = p * p % n
			if p == 1:
				return gcd(prev - 1, n)
			if p == n - 1:
				break
		else:
			for i in range(2, n):
				(x, y) = (i, (i * i + 1) % n)
				f = gcd(abs(x - y), n)
				while f == 1:
					(x, y) = ((x * x + 1) % n, (y * y + 1) % n)
					y = (y * y + 1) % n
					f = gcd(abs(x - y), n)
				if f != n:
					return f
	return n

@memodict
def prime_factors(n):
	if n <= 1:
		return Counter()
	f = pollard_rho(n)
	return Counter([n]) if f == n else prime_factors(f) + prime_factors(n // f)

def distinct_factors(n):
	factors = [1]
	for (p, exp) in prime_factors(n).items():
		factors += [p ** i * factor for factor in factors for i in range(1, exp + 1)]
	return factors

def all_factors(n):
	(small, large) = ([], [])
	for i in range(1, int(n ** 0.5) + 1, 2 if n & 1 else 1):
		if not n % i:
			small.append(i)
			large.append(n // i)
	if small[-1] == large[-1]:
		large.pop()
	large.reverse()
	small.extend(large)
	return small
	return ans

def main():
	mod = 1000000007
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = 1
	tc = 1
	for _ in range(tc):
		(n, m) = ria()
		t = ria()
		cnt = [0] * 101
		s = 0
		ans = []
		for i in range(n):
			d = s + t[i] - m
			k = 0
			if d > 0:
				for j in range(100, 0, -1):
					x = j * cnt[j]
					if d <= x:
						k += (d + j - 1) // j
						break
					k += cnt[j]
					d -= x
			s += t[i]
			cnt[t[i]] += 1
			ans.append(k)
		wia(ans)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


import math

def main():
	(n, m) = map(int, input().split())
	time = list(map(int, input().split()))
	ans = []
	total = 0
	counts = [0] * 100
	for i in range(n):
		if m - total >= time[i]:
			ans.append(0)
		else:
			count = 0
			new = total
			for j in range(99, -1, -1):
				if counts[j] > 0:
					new -= counts[j] * (j + 1)
					if m - new < time[i]:
						count += counts[j]
					else:
						new += counts[j] * (j + 1)
						count += math.ceil((time[i] + new - m) / (j + 1))
						break
			ans.append(count)
		counts[time[i] - 1] += 1
		total += time[i]
	for i in ans:
		print(i, end=' ')
main()


import sys

def nline():
	return sys.stdin.readline()[:-1]

def ni():
	return int(sys.stdin.readline())

def na():
	return [int(v) for v in sys.stdin.readline().split()]
(n, m) = na()
arr = na()
sm = 0
count = [0] * 101
for i in range(0, n):
	(diff, k) = (sm + arr[i] - m, 0)
	if diff > 0:
		for j in range(100, -1, -1):
			tmp = count[j] * j
			if tmp >= diff:
				k += (diff + j - 1) // j
				break
			k += count[j]
			diff -= tmp
	print(k, end=' ')
	sm += arr[i]
	count[arr[i]] += 1


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(RL())

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)

def toord(c):
	return ord(c) - ord('a')

def lcm(a, b):
	return a * b // gcd(a, b)
mod = 998244353
INF = float('inf')
from math import factorial, sqrt, ceil, floor, gcd
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def main():
	(n, m) = RL()
	arr = RLL()
	sm = [0]
	rec = [0] * 101
	for i in range(n):
		sm.append(sm[-1] + arr[i])
	res = []
	for i in range(1, n + 1):
		if sm[i] <= m:
			res.append(0)
		else:
			now = sm[i]
			tmp = 0
			dif = now - m
			for j in range(100, 0, -1):
				if rec[j] == 0:
					continue
				num = rec[j]
				use = min(num, ceil(dif / j))
				tmp += use
				dif -= use * j
				if dif <= 0:
					break
			res.append(tmp)
		rec[arr[i - 1]] += 1
	print(*res)
main()


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = {}
for i in range(1, 101):
	b[i] = 0
for i in range(n):
	su = a[i]
	(cn, fg) = (1, 0)
	for j in range(1, 101):
		if su + j * b[j] > m:
			break
		cn = cn + b[j]
		su += b[j] * j
	else:
		fg = 1
	if fg == 0:
		cn += (m - su) // j
		su += j * ((m - su) // j)
	b[a[i]] += 1
	print(i + 1 - cn, end=' ')


from sys import stdin
input = lambda : stdin.readline().rstrip('\r\n')
(n, m) = map(int, input().split())
t = list(map(int, input().split()))
pre = [0]
ans = []
d = {}
for i in range(1, 101):
	d[i] = 0
for i in range(n):
	if pre[-1] + t[i] <= m:
		ans.append(0)
	else:
		x = pre[-1] + t[i] - m
		c = 0
		for j in range(100, 0, -1):
			if x <= j * d[j]:
				c += (x + j - 1) // j
				ans.append(c)
				break
			else:
				x -= j * d[j]
				c += d[j]
	pre.append(pre[-1] + t[i])
	d[t[i]] += 1
print(*ans)


(n, m) = list(map(int, input().split()))
arr = list(map(int, input().split()))
pre = [arr[0]]
for i in range(1, n):
	pre.append(pre[-1] + arr[i])
ans = []
freq = [0 for i in range(105)]
for i in range(n):
	if pre[i] <= m:
		ans.append(0)
	else:
		x = pre[i]
		cnt = 0
		d = x - m
		for j in range(104, 0, -1):
			if freq[j] > 0:
				if freq[j] * j <= d:
					d -= j * freq[j]
					cnt += freq[j]
				elif d % j == 0:
					y = d // j
					cnt += y
					d = 0
				else:
					y = d // j + 1
					cnt += y
					d = 0
			if d == 0:
				break
		ans.append(cnt)
	freq[arr[i]] += 1
print(*ans)


import math
import heapq
import copy
from collections import OrderedDict
from collections import deque
t = list(map(int, input().split()))
d = t[1]
k = list(map(int, input().split()))
m = [0] * 101
ans = list()
time = 0
for i in range(t[0]):
	time = time + k[i]
	if d - time >= 0:
		ans.append(0)
		m[k[i]] = m[k[i]] + 1
	else:
		count = 0
		test = time
		for j in range(100, -1, -1):
			if test <= d:
				break
			if m[j] > 0:
				cur = m[j]
				vv = cur * j
				if abs(test - vv) <= d:
					if vv < test or vv > test:
						x = math.ceil((test - d) / j)
						if x <= cur:
							count = count + x
							test = test - x * j
						else:
							count = count + cur
							test = test - cur * j
					else:
						count = count
						test = test - vv
				else:
					count = count + m[j]
					test = test - vv
		ans.append(count)
		m[k[i]] = m[k[i]] + 1
print(*ans)


from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, groupby
import sys
import bisect
import string
import math
import time
import random

def S_():
	return input()

def LS():
	return [i for i in input().split()]

def I():
	return int(input())

def MI():
	return map(int, input().split())

def LI():
	return [int(i) for i in input().split()]

def LI_():
	return [int(i) - 1 for i in input().split()]

def NI(n):
	return [int(input()) for i in range(n)]

def NI_(n):
	return [int(input()) - 1 for i in range(n)]

def StoI():
	return [ord(i) - 97 for i in input()]

def ItoS(nn):
	return chr(nn + 97)

def LtoS(ls):
	return ''.join([chr(i + 97) for i in ls])

def GI(V, E, Directed=False, index=0):
	org_inp = []
	g = [[] for i in range(n)]
	for i in range(E):
		inp = LI()
		org_inp.append(inp)
		if index == 0:
			inp[0] -= 1
			inp[1] -= 1
		if len(inp) == 2:
			(a, b) = inp
			g[a].append(b)
			if not Directed:
				g[b].append(a)
		elif len(inp) == 3:
			(a, b, c) = inp
			aa = (inp[0], inp[2])
			bb = (inp[1], inp[2])
			g[a].append(bb)
			if not Directed:
				g[b].append(aa)
	return (g, org_inp)

def bit_combination(k, n=2):
	rt = []
	for tb in range(n ** k):
		s = [tb // n ** bt % n for bt in range(k)]
		rt += [s]
	return rt

def show(*inp, end='\n'):
	if show_flg:
		print(*inp, end=end)
YN = ['Yes', 'No']
mo = 10 ** 9 + 7
inf = float('inf')
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10 ** 5)
input = lambda : sys.stdin.readline().rstrip()

def ran_input():
	import random
	n = random.randint(4, 16)
	(rmin, rmax) = (1, 10)
	a = [random.randint(rmin, rmax) for _ in range(n)]
	return (n, a)
show_flg = False
show_flg = True
ans = 0
(n, m) = LI()
t = LI()
c = [0] * 101
T = 0
for i in range(n):
	R = T
	ans = 0
	for j in range(101)[::-1]:
		if m - (R - c[j] * j) >= t[i]:
			if t[i] - (m - R) > 0:
				ans += (t[i] - (m - R) + j - 1) // j
			print(ans)
			break
		ans += c[j]
		R -= c[j] * j
	T += t[i]
	c[t[i]] += 1


from sys import *
from collections import defaultdict as dd
from math import *
from bisect import *

def sinp():
	return input()

def inp():
	return int(sinp())

def minp():
	return map(int, sinp().split())

def linp():
	return list(minp())

def strl():
	return list(sinp())

def pr(x):
	print(x)
mod = int(1000000000.0 + 7)
(n, m) = minp()
t = linp()
res = []
s = 0
d = dd(int)
for i in range(n):
	s += t[i]
	c = 0
	if s <= m:
		res.append(0)
	else:
		temp = sorted(list(d.keys()))
		sum = 0
		for j in range(len(temp) - 1, -1, -1):
			sum += temp[j] * d[temp[j]]
			c += d[temp[j]]
			if sum > s - m:
				sum -= temp[j] * d[temp[j]]
				c -= d[temp[j]]
				c += ceil((s - m - sum) / temp[j])
				break
		res.append(c)
	d[t[i]] += 1
print(*res)


(n, m) = [int(i) for i in input().split()]
line = [int(x) for x in input().split()]
count = {i + 1: 0 for i in range(100)}
sum = 0
for i in line:
	p = sum + i
	t = 0
	if p > m:
		for j in range(100, 0, -1):
			if count[j] == 0:
				continue
			elif p - count[j] * j > m:
				p -= count[j] * j
				t += count[j]
			else:
				l = (p - m) // j
				if p - l * j > m:
					l += 1
				t += l
				break
	count[i] += 1
	sum += i
	print(t, end=' ')


from sys import stdout
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
dp = 0
size = max(a) + 1
b = [0] * size
for i in range(n):
	e = a[i]
	k = 1
	c = 0
	s_c = m - e
	while k < size:
		if b[k] != 0:
			if s_c < b[k] * k:
				c += s_c // k
				break
			else:
				s_c -= b[k] * k
				c += b[k]
		k += 1
	b[e] += 1
	stdout.write(str(i - c) + ' ')


import math
(n, M) = map(int, input().split())
ti = list(map(int, input().split()))
li = [0 for _ in range(101)]
ans = []
summ = 0
for i in ti:
	summ += i
	su = summ
	count = 0
	if su > M:
		for ii in range(100, -1, -1):
			if su <= M:
				break
			elif su - li[ii] * ii > M:
				count += li[ii]
				su -= li[ii] * ii
			else:
				count += math.ceil((su - M) / ii)
				su -= math.ceil((su - M) / ii) * ii
				break
	ans.append(count)
	li[i] += 1
print(*ans)


(n, M) = map(int, input().split())
ls = list(map(int, input().split()))
count = {}
for i in range(1, 101):
	count[i] = 0
for i in range(n):
	Sum = ls[i]
	cnt = 1
	flag = 0
	for j in range(1, 101):
		if Sum + j * count[j] > M:
			break
		Sum += j * count[j]
		cnt += count[j]
	else:
		flag = 1
	if flag == 0:
		cnt += (M - Sum) // j
		Sum += j * ((M - Sum) // j)
	count[ls[i]] += 1
	print(i + 1 - cnt, end=' ')
print()


from sys import *
buckets = [0] * 101
(n, M) = map(int, stdin.readline().split())
ts = [int(t) for t in stdin.readline().split()]
full_sum = 0
for i in range(n):
	cur_M = M
	cur_sum = full_sum
	bucket_idx = 100
	ans = 0
	while cur_sum > cur_M - ts[i]:
		if cur_sum - cur_M + ts[i] >= buckets[bucket_idx] * bucket_idx:
			cur_sum -= buckets[bucket_idx] * bucket_idx
			ans += buckets[bucket_idx]
		else:
			tmp = (cur_sum - cur_M + ts[i] - 1) // bucket_idx + 1
			ans += tmp
			cur_sum -= bucket_idx * tmp
		bucket_idx -= 1
	stdout.write(str(ans) + ' ')
	full_sum += ts[i]
	buckets[ts[i]] += 1
stdout.write('\n')


(n, m) = map(int, input().strip().split())
a = [int(x) for x in input().strip().split()]
t = [0 for i in range(0, 101)]
for i in range(0, n):
	(c, j, s) = (a[i], 1, 0)
	flag = 0
	while j < 101:
		cnt = min(t[j], (m - c) // j)
		s += cnt
		c += j * cnt
		if cnt < t[j]:
			flag = 1
			break
		j += 1
	if flag == 0:
		print(0, end=' ')
	else:
		print(i - s, end=' ')
	t[a[i]] += 1


from itertools import accumulate
from collections import Counter
from bisect import bisect as br, bisect_left as bl

class PMS:

	def __init__(self, A, B, issum=False):
		(self.X, self.comp) = self.compress(B)
		self.size = len(self.X)
		self.tree = [0] * (self.size + 1)
		self.p = 2 ** (self.size.bit_length() - 1)
		self.dep = self.size.bit_length()
		CA = Counter(A)
		S = [0] + list(accumulate([CA[self.X[i]] for i in range(self.size)]))
		for i in range(1, 1 + self.size):
			self.tree[i] = S[i] - S[i - (i & -i)]
		if issum:
			self.sumtree = [0] * (self.size + 1)
			Ssum = [0] + list(accumulate([CA[self.X[i]] * self.X[i] for i in range(self.size)]))
			for i in range(1, 1 + self.size):
				self.sumtree[i] = Ssum[i] - Ssum[i - (i & -i)]

	def compress(self, L):
		L2 = list(set(L))
		L2.sort()
		C = {v: k for (k, v) in enumerate(L2, 1)}
		return (L2, C)

	def leng(self):
		return self.count(self.X[-1])

	def count(self, i):
		i = self.comp[i]
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def less(self, v):
		i = bl(self.X, v)
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def leq(self, v):
		i = br(self.X, v)
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		i = self.comp[i]
		while i <= self.size:
			self.tree[i] += x
			i += i & -i

	def get(self, v):
		if v <= 0:
			return -1
		s = 0
		k = self.p
		for _ in range(self.dep):
			if s + k <= self.size and self.tree[s + k] < v:
				s += k
				v -= self.tree[s]
			k //= 2
		return self.X[s]

	def gets(self, v):
		v1 = v
		if v <= 0:
			return 0
		s = 0
		k = self.p
		for _ in range(self.dep):
			if s + k <= self.size and self.sumtree[s + k] < v:
				s += k
				v -= self.sumtree[s]
			k //= 2
		if s == self.size:
			return self.leng()
		return self.count(self.X[s]) + (v1 - self.countsum(self.X[s])) // self.X[s]

	def addsum(self, i, x):
		self.add(i, x)
		x *= i
		i = self.comp[i]
		while i <= self.size:
			self.sumtree[i] += x
			i += i & -i

	def countsum(self, i):
		i = self.comp[i]
		s = 0
		while i > 0:
			s += self.sumtree[i]
			i -= i & -i
		return s

	def getsum(self, v):
		x = self.get(v)
		return self.countsum(x) - x * (self.count(x) - v)
(N, M) = map(int, input().split())
T = list(map(int, input().split()))
S = PMS([T[0]], T, True)
print(0)
for i in range(1, N):
	print(i - S.gets(M - T[i]))
	S.addsum(T[i], 1)


from heapq import *
(N, M) = map(int, input().split())
A = [int(a) for a in input().split()]
h = []
s = 0
k = 0
ANS = []
for a in A:
	t = []
	while s + a > M:
		t.append(heappop(h))
		s += t[-1]
	ANS.append(len(t) + k)
	while t:
		s -= t[-1]
		heappush(h, t.pop())
	s += a
	heappush(h, -a)
	if s > M:
		s += heappop(h)
		k += 1
print(*ANS)


a = [int(i) for i in input().split()]
n = a[0]
M = a[1]
x = [int(i) for i in input().split()]
pref = [0 for i in x]
pref[0] = x[0]
freq = [0 for i in range(100)]
for i in range(1, n):
	pref[i] = pref[i - 1] + x[i]
for j in range(n):
	ans = pref[j]
	if ans <= M:
		print(0, end=' ')
	else:
		k = 0
		while ans > M:
			for i in range(99, -1, -1):
				if freq[i] == 0:
					continue
				y = (ans - M) // (i + 1)
				if y == 0:
					ans = ans - (i + 1)
					k += 1
				elif freq[i] <= y:
					ans = ans - freq[i] * (i + 1)
					k += freq[i]
				elif ans - y * (i + 1) <= M:
					ans = ans - y * (i + 1)
					k += y
				else:
					ans = ans - (y + 1) * (i + 1)
					k += y + 1
				if ans <= M:
					break
		print(k, end=' ')
	freq[x[j] - 1] += 1


from sys import stdin, stdout
from math import gcd, sqrt, factorial, pi, inf
from collections import deque, defaultdict
from bisect import bisect, bisect_left
from time import time
from itertools import permutations as per
from heapq import heapify, heappush, heappop, heappushpop
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\r\n')
L = lambda : list(R())
P = lambda x: stdout.write(str(x) + '\n')
lcm = lambda x, y: x * y // gcd(x, y)
nCr = lambda x, y: f[x] * inv(f[y] * f[x - y] % N) % N
inv = lambda x: pow(x, N - 2, N)
sm = lambda x: (x ** 2 + x) // 2
N = 10 ** 9 + 7

def get_ans(x):
	ans = 0
	stk = deque([0])
	while stk and x:
		v = stk.pop()
		if tr[v][0] >= x:
			if v < p - 1:
				stk.append(v * 2 + 1)
				stk.append(v * 2 + 2)
			else:
				x = 0
				ans += tr[v][1]
		else:
			x -= tr[v][0]
			ans += tr[v][1]
	return ans

def update(x):
	id = p - 1 + ind[x].pop()
	while id != -1:
		tr[id][0] += x
		tr[id][1] += 1
		id = pr[id]
(n, m) = R()
p = 1
while p <= n:
	p <<= 1
tr = [[0, 0] for i in range((p << 1) - 1)]
pr = [0] * ((p << 1) - 1)
pr[0] = -1
for i in range(p - 1):
	pr[(i << 1) + 1] = i
	pr[(i << 1) + 2] = i
a = L()
ind = [[] for i in range(105)]
for (i, j) in enumerate(sorted(a)):
	ind[j] += (i,)
for i in a:
	if tr[0][0] + i > m:
		print(get_ans(tr[0][0] - (m - i)), end=' ')
	else:
		print(0, end=' ')
	update(i)


(n, m) = map(int, input().split())
c = [0] * 101
a = list(map(int, input().split()))
for i in range(n):
	ans = 0
	sm = a[i]
	for j in range(1, 101):
		k = min((m - sm) // j, c[j])
		ans += k
		sm += k * j
	print(i - ans)
	c[a[i]] += 1


x = list(map(int, input().rstrip().split()))
y = list(map(int, input().rstrip().split()))
l = [0] * 101
out = [0] * x[0]
su = 0
for i in range(x[0]):
	k = 0
	d = su + y[i] - x[1]
	if d > 0:
		for j in range(100, 0, -1):
			h = j * l[j]
			if d <= h:
				k += (d + j - 1) // j
				break
			k += l[j]
			d -= h
	su += y[i]
	l[y[i]] += 1
	print(k)


(n, M) = map(int, input().split())
a = list(map(int, input().split()))
b = [0] * 110
for x in a:
	cc = 0
	cur = 0
	for j in range(1, 101):
		h = min((M - x - cur) // j, b[j])
		cc += h
		cur += h * j
	b[x] += 1
	print(sum(b) - cc - 1)


import itertools
from heapq import heapify, heappush, heappop
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
t = list(map(int, input().split()))
tsum = list(itertools.accumulate(t))
ans = []
for i in range(n):
	if tsum[i] <= m:
		ans.append(0)
	else:
		heap = [-k for k in t[:i]]
		heapify(heap)
		remain = sum(t[:i]) - m
		count = 0
		for j in range(i, n):
			uselist = []
			remain += t[j]
			while remain > 0:
				count += 1
				use = heappop(heap)
				remain += use
				uselist.append(use)
			else:
				ans.append(count)
				uselist.sort(reverse=True)
			summ = 0
			for uses in uselist[:100]:
				heappush(heap, uses)
				remain -= uses
				summ -= uses
				count -= 1
				if summ > 100:
					break
			heappush(heap, -t[j])
		break
print(' '.join(map(str, ans)))


from heapq import *
(n, m) = map(int, input().split())
t = [int(x) for x in input().split()]
cnt = [0] * 101
mx = [0] * 101
res = []
ct = 0
for i in range(n):
	if ct + t[i] <= m:
		res.append('0')
	else:
		nd = m - t[i]
		rem = 0
		for j in range(1, 101):
			if nd >= mx[j]:
				nd -= mx[j]
				rem += cnt[j]
			else:
				rem += nd // j
				nd = 0
			if nd == 0:
				break
		res.append(str(i - rem))
	cnt[t[i]] += 1
	mx[t[i]] += t[i]
	ct += t[i]
print(' '.join(res))


from copy import deepcopy
iarr = list(map(int, input().split()))
n = iarr[0]
m = iarr[1]
tar = list(map(int, input().split()))
freq = [0 for i in range(101)]
for i in range(n):
	rem = m - tar[i]
	count = 0
	counthr = 0
	for j in range(1, 101):
		afteradd = counthr + freq[j] * j
		if afteradd > rem:
			count += (rem - counthr) // j
			counthr += count * j
			break
		elif afteradd == rem:
			counthr = afteradd
			count += freq[j]
			break
		else:
			counthr = afteradd
			count += freq[j]
	freq[tar[i]] += 1
	print(i - count, end=' ')
print()


(n, m) = map(int, input().split())
array = list(map(int, input().split()))
counts = [0] * 101
answer = []
s = 0
for i in range(n):
	s += array[i]
	ans = 0
	s_in_iteration = s - m
	for j in range(100, 0, -1):
		if s_in_iteration > 0:
			count = (s_in_iteration + j - 1) // j
			if count > counts[j]:
				s_in_iteration -= counts[j] * j
				ans += counts[j]
			else:
				ans += count
				break
		else:
			break
	answer.append(ans)
	counts[array[i]] += 1
print(*answer)


R = lambda : map(int, input().split())
(n, m) = R()
cnts = [0] * 105
tcnt = 0
for x in R():
	cnt = acc = 0
	for (i, c) in enumerate(cnts):
		if acc + i * c + x <= m:
			(cnt, acc) = (cnt + c, acc + i * c)
		else:
			cnt += (m - acc - x) // i
			break
	print(tcnt - cnt, end=' ')
	cnts[x] += 1
	tcnt += 1


(n, m) = map(int, input().split())
(tot_sum, curr_sum, d) = (0, 0, {})
arr = list(map(int, input().split()))
for x in arr:
	tot_sum += x
	curr_sum += x
	curr_res = 0
	for it in sorted(d.keys(), reverse=True):
		if curr_sum <= m:
			break
		take = min(d[it], (curr_sum - m + it - 1) // it)
		curr_sum -= take * it
		curr_res += take
	d[x] = 1 if x not in d else d[x] + 1
	curr_sum = tot_sum
	print(curr_res, end=' ')


(n, t) = map(int, input().split())
arr = [0] * 101
students = [int(x) for x in input().split()]
cur_time = 0
for i in students:
	cur_time += i
	ptr = 100
	this = cur_time
	acc = 0
	while ptr:
		if this - arr[ptr] * ptr <= t:
			acc += (this - t - 1) // ptr + 1
			break
		else:
			acc += arr[ptr]
			this -= arr[ptr] * ptr
		ptr -= 1
	print(max(0, acc), end=' ')
	arr[i] += 1


def ri():
	return [int(i) for i in input().split()]

def fl(a, b):
	return abs(a - b)

def gt_mx(d, l):
	ans = 0
	for i in reversed(range(1, 110)):
		if l < 0:
			break
		if d[i] > 0:
			do = min(l // i, d[i])
			ans += do
			l -= do * i
			if l > 0 and do < d[i]:
				l -= i
				ans += 1
	return ans

def main(n, m, t):
	if m >= t[0]:
		print(0, end=' ')
	else:
		print(1, end=' ')
	d = {i: 0 for i in range(1, 110)}
	d[t[0]] += 1
	sm = t[0]
	for i in range(1, len(t)):
		sm += t[i]
		if i == 5:
			asd = 123
		if sm > m:
			delit = gt_mx(d, sm - m)
			print(delit, end=' ')
		else:
			print(0, end=' ')
		d[t[i]] += 1
(n, m) = ri()
t = ri()
main(n, m, t)


(n, m) = map(int, input().split())
t = list(map(int, input().split()))
tIndex = {}
tIndexSum = {}
s = 0
for i in range(n):
	r = 0
	if s + t[i] > m:
		keys = list(tIndex.keys())
		keys.sort(reverse=True)
		s1 = s
		for k in keys:
			if s1 - tIndex[k] * k + t[i] > m:
				s1 -= tIndex[k] * k
				r += tIndex[k]
			else:
				r += (s1 + t[i] - m) // k
				s1 -= (s1 + t[i] - m) // k * k
				if s1 + t[i] > m:
					s1 -= k
					r += 1
			if s1 + t[i] <= m:
				break
	print(r, end=' ')
	if not t[i] in tIndex:
		tIndex[t[i]] = 0
	tIndex[t[i]] += 1
	if not t[i] in tIndexSum:
		tIndexSum[t[i]] = 0
	tIndexSum[t[i]] += t[i]
	s += t[i]


from sys import stdin, stdout
import math
import collections
(n, m) = list(map(int, stdin.readline().split()))
arr = list(map(int, stdin.readline().split()))
aux = dict()
for i in range(1, 101):
	aux[i] = 0
cur_sum = 0
for i in range(len(arr)):
	count = 0
	if cur_sum + arr[i] <= m:
		count = 0
	else:
		temp = 0
		for k in range(100, 0, -1):
			temp += k * aux[k]
			if cur_sum - temp + arr[i] <= m:
				temp -= k * aux[k]
				start = 1
				end = aux[k]
				while True:
					if start >= end:
						if cur_sum - temp - (start - 1) * k + arr[i] <= m:
							start -= 1
							break
						break
					mid = (start + end) // 2
					if cur_sum - mid * k - temp + arr[i] <= m:
						end = mid - 1
					else:
						start = mid + 1
				if cur_sum - start * k - temp + arr[i] <= m:
					count += start
					break
				else:
					count += start + 1
					break
			else:
				count += aux[k]
	cur_sum += arr[i]
	print(count, end=' ')
	aux[arr[i]] += 1


from sys import stdin, stdout
from itertools import accumulate
import math
(n, M) = stdin.readline().strip().split(' ')
(n, M) = (int(n), int(M))
ti = list(map(int, stdin.readline().strip().split(' ')))
ps_ti = list(accumulate(ti))
tarr = [0 for i in range(101)]
ansarr = []
for j in range(len(ti)):
	if ps_ti[j] <= M:
		ansarr.append('0')
		tarr[ti[j]] += 1
	else:
		rm = 0
		diff = ps_ti[j] - M
		for i in range(100, 0, -1):
			if tarr[i] == 0:
				continue
			elif diff <= i * tarr[i]:
				rm += math.ceil(diff / i)
				break
			else:
				diff -= i * tarr[i]
				rm += tarr[i]
		ansarr.append(str(rm))
		tarr[ti[j]] += 1
stdout.write(' '.join(ansarr))


(n, m) = map(int, input().split())
s = list(map(int, input().split()))
sas = s.copy()
g = 0
ans = []
for i in range(1, len(s)):
	s[i] += s[i - 1]
h = [0 for i in range(101)]
for i in range(len(s)):
	g = 0
	if s[i] <= m:
		ans.append(0)
	else:
		posos = s[i] - m
		for j in range(100, -1, -1):
			if h[j] * j >= posos:
				ans.append((posos + j - 1) // j + g)
				break
			elif h[j] > 0:
				g += h[j]
				posos -= h[j] * j
	h[sas[i]] += 1
print(*ans)


import bisect
(n, m) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
answer = []
students = [0] * 100
for i in range(n):
	time = m - a[i]
	counter = 0
	for j in range(100):
		x = min(time // (j + 1), students[j])
		counter += x
		time -= x * (j + 1)
	answer.append(i - counter)
	students[a[i] - 1] += 1
print(*answer)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import math
(n, M) = map(int, input().split())
l = list(map(int, input().split()))
k = [0] * 100
a = [0] * (n + 1)
ans = []
for i in range(1, n + 1):
	a[i] += a[i - 1] + l[i - 1]
for i in range(1, n + 1):
	if a[i] <= M:
		ans.append(0)
	else:
		asi = 0
		for j in range(99, -1, -1):
			if a[i] - k[j] * (j + 1) > M:
				a[i] -= k[j] * (j + 1)
				asi += k[j]
			else:
				asi += math.ceil((a[i] - M) / (j + 1))
				break
		ans.append(int(asi))
	k[l[i - 1] - 1] += 1
print(*ans, sep=' ')


R = lambda : map(int, input().split())
(n, m) = R()
L = list(R())
f = [0] * 101
su = 0
for i in range(n):
	su += L[i]
	p = su - m
	c = 0
	if p > 0:
		for j in reversed(range(1, 101)):
			if f[j] > 0:
				if p < f[j] * j:
					c += (p + j - 1) // j
					break
				else:
					c += f[j]
					p -= j * f[j]
	print(c, end=' ')
	f[L[i]] += 1


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
t = list(map(int, input().split()))
cnt = [0] * 101
cs = 0
ans = []
for i in range(n):
	r = cs - m + t[i]
	res = 0
	if r > 0:
		for j in range(1, 101)[::-1]:
			if r - cnt[j] * j > 0:
				r -= cnt[j] * j
				res += cnt[j]
			else:
				res += (r + j - 1) // j
				break
	ans.append(res)
	cs += t[i]
	cnt[t[i]] += 1
print(*ans)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
ans = []
ma = 0
tc = [0] * (max(a) + 1)
for (i, k) in enumerate(a):
	tcm = 0
	dop = 0
	ma = m - k
	for j in range(1, len(tc)):
		if ma < tcm + tc[j] * j:
			dop += (ma - tcm) // j
			break
		else:
			tcm += tc[j] * j
			dop += tc[j]
	ans.append(i - dop)
	tc[k] += 1
print(*ans)


def mp():
	return map(int, input().split())
(n, m) = mp()
a = list(mp())
s = [0] * (n + 1)
for i in range(n):
	s[i] = s[i - 1] + a[i]
cnt = [0] * 101
for i in range(n):
	ans = 0
	t = s[i]
	while t > m:
		for j in range(100, 0, -1):
			if cnt[j] != 0:
				k = max(0, (t - m + j - 1) // j)
				ans += min(k, cnt[j])
				t -= min(k, cnt[j]) * j
	cnt[a[i]] += 1
	print(ans, end=' ')


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, t) = map(int, input().split())
a = list(map(int, input().split()))
count = [0] * 101
s = 0
res = list()
for i in a:
	if i + s <= t:
		res.append(0)
	else:
		d = i + s - t
		ct = 0
		for j in range(100, 0, -1):
			if count[j] > 0:
				m = min(count[j], math.ceil(d / j))
				ct += m
				d -= m * j
			if d <= 0:
				break
		res.append(ct)
	count[i] += 1
	s += i
print(*res)


import math
(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
prefix = [0] * n
count = [0] * 101
for i in range(101):
	count[i] = [0] * 200001
for i in range(n):
	prefix[i] = prefix[i - 1] + arr[i]
	for j in range(1, 101):
		count[j][i] = count[j][i - 1]
		if j == arr[i]:
			count[j][i] += 1
for i in range(n):
	if prefix[i] <= m:
		print(0, end=' ')
	else:
		ct = 0
		sm = prefix[i]
		for j in range(100, 0, -1):
			if sm - count[j][i - 1] * j > m:
				ct += count[j][i - 1]
				sm -= count[j][i - 1] * j
			else:
				ct += math.ceil((sm - m) / j)
				print(ct, end=' ')
				break


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
mod2 = 998244353
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))

def IF(c, t, f):
	return t if c else f

def YES(c):
	return IF(c, 'YES', 'NO')

def Yes(c):
	return IF(c, 'Yes', 'No')

def main():
	t = 1
	rr = []
	for _ in range(t):
		(n, m) = LI()
		a = LI()
		r = []
		t = 0
		q1 = []
		q2 = []
		for (i, c) in enumerate(a):
			if q1 and q2:
				t1 = -heapq.heappop(q1)
				t -= t1
				while q2:
					t2 = heapq.heappop(q2)
					if t2 < t1 and t + t2 + c <= m:
						t += t2
						heapq.heappush(q1, -t2)
					else:
						heapq.heappush(q2, t2)
						break
				if t + t1 + c <= m:
					t += t1
					heapq.heappush(q1, -t1)
				else:
					heapq.heappush(q2, t1)
			while t + c > m:
				t1 = -heapq.heappop(q1)
				t -= t1
				heapq.heappush(q2, t1)
			t += c
			heapq.heappush(q1, -c)
			r.append(i + 1 - len(q1))
		rr.append(JA(r, ' '))
	return JA(rr, '\n')
print(main())


import math
(n, m) = map(int, input().split())
t = [0] * 101
l = list(map(int, input().split()))
ans = []
cur = 0
for i in range(n):
	cur += l[i]
	if cur <= m:
		print(0, end=' ')
		t[l[i]] += 1
	else:
		sa = cur - m
		count = 0
		for j in range(100, 0, -1):
			if t[j] > 0:
				val = sa // j
				if sa % j != 0:
					val += 1
				if val <= t[j]:
					sa -= j * val
					count += val
				else:
					sa -= t[j] * j
					count += t[j]
			if sa <= 0:
				break
		print(count, end=' ')
		t[l[i]] += 1