Petya has an array $a$ consisting of $n$ integers. He has learned partial sums recently, and now he can calculate the sum of elements on any segment of the array really fast. The segment is a non-empty sequence of elements standing one next to another in the array.

Now he wonders what is the number of segments in his array with the sum less than $t$. Help Petya to calculate this number.

More formally, you are required to calculate the number of pairs $l, r$ ($l \le r$) such that $a_l + a_{l+1} + \dots + a_{r-1} + a_r < t$.


-----Input-----

The first line contains two integers $n$ and $t$ ($1 \le n \le 200\,000, |t| \le 2\cdot10^{14}$).

The second line contains a sequence of integers $a_1, a_2, \dots, a_n$ ($|a_{i}| \le 10^{9}$) — the description of Petya's array. Note that there might be negative, zero and positive elements.


-----Output-----

Print the number of segments in Petya's array with the sum of elements less than $t$.


-----Examples-----
Input
5 4
5 -1 3 4 -1

Output
5

Input
3 0
-1 2 -3

Output
4

Input
4 -1
-2 1 -2 3

Output
3



-----Note-----

In the first example the following segments have sum less than $4$:  $[2, 2]$, sum of elements is $-1$  $[2, 3]$, sum of elements is $2$  $[3, 3]$, sum of elements is $3$  $[4, 5]$, sum of elements is $3$  $[5, 5]$, sum of elements is $-1$

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Data structures

Amortized analysis

Divide and conquer


Solutions:
from itertools import accumulate, chain

class Fenwick:

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

	def update(self, i, val):
		i += 1
		while i < len(self.tree):
			self.tree[i] += 1
			i += i & -i

	def get(self, i):
		i += 1
		total = 0
		while i > 0:
			total += self.tree[i]
			i -= i & -i
		return total

def solution(n, a, t):
	S = [s for s in accumulate(a)]
	T = [[s, s - t] for s in S]
	T = list(set(chain(*T)))
	T.sort()
	T = {v: i for (i, v) in enumerate(T)}
	fenwick = Fenwick(len(T))
	total = 0
	for (i, v) in enumerate(S):
		diff = v - t
		total += i - fenwick.get(T[diff])
		if v < t:
			total += 1
		fenwick.update(T[v], 1)
	return total
f = lambda : [int(c) for c in input().split()]
(n, t) = f()
a = f()
print(solution(n, a, t))


maxn = 2 * 10 ** 5 + 5
bit = [0] * maxn

def add(idx):
	idx += 1
	while idx < maxn:
		bit[idx] += 1
		idx += idx & -idx

def sm(idx):
	idx += 1
	tot = 0
	while idx > 0:
		tot += bit[idx]
		idx -= idx & -idx
	return tot
(n, t) = map(int, input().split())
a = list(map(int, input().split()))
psum = [0] * (n + 1)
for i in range(n):
	psum[i + 1] = psum[i] + a[i]
psum.sort(reverse=True)
upsum = [-10 ** 18]
for i in range(n + 1):
	if i == 0 or psum[i] != psum[i - 1]:
		upsum.append(psum[i])
upsum.sort(reverse=True)

def lower_bound(i):
	l = 0
	r = len(upsum) - 1
	while l != r:
		m = (l + r) // 2
		if upsum[m] <= i:
			r = m
		else:
			l = m + 1
	return l
ans = 0
curr = 0
add(lower_bound(0))
for i in a:
	curr += i
	ans += sm(lower_bound(curr - t) - 1)
	add(lower_bound(curr))
print(ans)


import bisect
(N, T) = list(map(int, input().split()))
A = [int(x) for x in input().split()]
prefsums = [0] * (N + 1)
for i in range(N):
	prefsums[i + 1] = A[i] + prefsums[i]
MAXNN = len(prefsums) + 1
L = [0] * MAXNN

def lsb(i):
	return i & -i

def update(i):
	while i < MAXNN:
		L[i] += 1
		i |= i + 1

def get(i):
	ans = 0
	while i >= 0:
		ans += L[i]
		i = (i & i + 1) - 1
	return ans
prefsums = list(sorted(set(prefsums)))
ans = 0
update(bisect.bisect_left(prefsums, 0))
pr = 0
for (i, v) in enumerate(A):
	pr += v
	npos = bisect.bisect_right(prefsums, pr - T)
	ans += i + 1 - get(npos - 1)
	k = bisect.bisect_left(prefsums, pr)
	update(k)
print(ans)


from bisect import bisect_left
from itertools import accumulate

def update(x, delta):
	seg_tree[x] += 1
	y = x >> 1
	while y > 0:
		seg_tree[y] = seg_tree[y << 1] + seg_tree[(y << 1) + 1]
		y = y >> 1

def query(x):
	ans = 0
	r = x
	l = n
	while l < r:
		if l % 2 == 1:
			ans += seg_tree[l]
			l += 1
		if r % 2 == 0:
			ans += seg_tree[r]
			r -= 1
		l = l >> 1
		r = r >> 1
	if l == r:
		ans += seg_tree[l]
	return ans
(n, t) = map(int, input().split())
arr = list(accumulate(list(map(int, input().split()))))
seg_tree = [0 for i in range(2 * n)]
post = list(sorted([-10 ** 19] + arr))
arr = [0] + arr
leftmost = dict()
for (idx, v) in enumerate(post):
	if v not in leftmost:
		leftmost[v] = idx
res = 0
for i in range(1, len(arr)):
	lower_idx = bisect_left(post, arr[i - 1] + t)
	res += lower_idx - query(n + lower_idx - 1 - 1) - 1
	update(n + leftmost[arr[i]] - 1, 1)
print(res)


(n, t) = map(int, input().split())
a = list(map(int, input().split()))
bit = [0 for i in range(n + 2)]

def qq(i):
	ans = 0
	i = i + 1
	while i > 0:
		ans += bit[i]
		i -= i & -i
	return ans

def u(i):
	i += 1
	while i <= n + 1:
		bit[i] += 1
		i += i & -i
q = []
c = [0]
for i in range(n):
	c.append(c[-1] + a[i])
	q.append((i + 1, t + c[i]))
c = [(c[i], i) for i in range(n + 1)]
c.sort()
q.sort(key=lambda x: x[1])
ans = 0
i = 0
j = 0
while j < len(q):
	(l, x) = q[j]
	while i <= n and c[i][0] < x:
		u(c[i][1])
		i += 1
	ans += qq(n) - qq(l - 1)
	j += 1
print(ans)


def merge(l, r):
	global num
	if l >= r:
		return
	mid = l + r >> 1
	merge(l, mid)
	merge(mid + 1, r)
	j = mid + 1
	for i in range(l, mid + 1):
		while j <= r and arr[j] - arr[i] < t:
			j += 1
		num += j - mid - 1
	arr[l:r + 1] = sorted(arr[l:r + 1])
(n, t) = map(int, input().split())
List = list(map(int, input().split()))
num = 0
arr = [0] * (n + 1)
for i in range(1, n + 1):
	arr[i] = arr[i - 1] + List[i - 1]
merge(0, n)
print(num)


from sys import stdin
from bisect import bisect_left

def read_bit(tree, idx):
	s = 0
	while idx > 0:
		s += tree[idx]
		idx -= idx & -idx
	return s

def update_bit(tree, idx, val):
	while idx < len(tree):
		tree[idx] += val
		idx += idx & -idx
(n, t) = map(int, stdin.readline().split())
a = [int(x) for x in stdin.readline().split()]
pref = [0] * n
pref[0] = a[0]
for i in range(1, n):
	pref[i] = pref[i - 1] + a[i]
pref.sort()
before = ans = 0
tree = [0] * (n + 2)
for i in range(n):
	ind = bisect_left(pref, t + before)
	if ind > 0:
		ans += ind - read_bit(tree, ind)
	before += a[i]
	before_ind = bisect_left(pref, before)
	update_bit(tree, before_ind + 1, 1)
print(ans)


import bisect

class BIT:

	def __init__(self, node_size):
		self._node = node_size + 1
		self.bit = [0] * self._node

	def add(self, index, add_val):
		while index < self._node:
			self.bit[index] += add_val
			index += index & -index

	def sum(self, index):
		res = 0
		while index > 0:
			res += self.bit[index]
			index -= index & -index
		return res
(n, t) = map(int, input().split())
a = list(map(int, input().split()))
ru = [0] * (n + 1)
ans = 0
for i in range(1, n + 1):
	ru[i] = ru[i - 1] + a[i - 1]
rus = sorted(ru)
bit = BIT(n + 2)
for i in range(n + 1):
	ru[i] = bisect.bisect_left(rus, ru[i])
for i in range(n + 1):
	ind = bisect.bisect_left(rus, rus[ru[i]] - t + 1)
	ans += bit.sum(n + 2) - bit.sum(ind)
	bit.add(ru[i] + 1, 1)
print(ans)


class segmentTree:
	initValue = 0
	dat = []
	lenTreeLeaf = -1
	depthTreeList = 0
	lenOriginalList = -1
	func = None
	funcPropagateToChild = None
	lazy = None
	N = -1

	def load(self, l):
		self.N = len(l)
		self.lenOriginalList = self.N
		self.depthTreeList = (self.N - 1).bit_length()
		self.lenTreeLeaf = 2 ** self.depthTreeList
		self.dat = [self.initValue] * (self.lenTreeLeaf * 2)
		self.lazy = [self.initValue] * (self.lenTreeLeaf * 2)
		for i in range(len(l)):
			self.dat[self.lenTreeLeaf - 1 + i] = l[i]
		self.build()

	def build(self):
		for i in range(self.lenTreeLeaf - 2, -1, -1):
			self.dat[i] = self.func(self.dat[2 * i + 1], self.dat[2 * i + 2])

	def addValue(self, ind, value):
		nodeId = self.lenTreeLeaf - 1 + ind
		self.dat[nodeId] += value
		self.setValue(ind, self.dat[nodeId])

	def setValue(self, ind, value):
		nodeId = self.lenTreeLeaf - 1 + ind
		self.dat[nodeId] = value
		while nodeId != 0:
			nodeId = (nodeId - 1) // 2
			self.dat[nodeId] = self.func(self.dat[nodeId * 2 + 1], self.dat[nodeId * 2 + 2])

	def nodelistFromLR(self, l, r, withchild=False):
		L = l + self.lenTreeLeaf >> 1
		R = r + self.lenTreeLeaf >> 1
		lc = 0 if l & 1 else (L & -L).bit_length()
		rc = 0 if r & 1 else (R & -R).bit_length()
		res = []
		for i in range(self.depthTreeList + (1 if withchild else 0)):
			if rc <= i:
				res.append(R - 1)
			if L < R and lc <= i:
				res.append(L - 1)
			L = L >> 1
			R = R >> 1
		return res

	def rangeAdd(self, l, r, x):
		plist = self.nodelistFromLR(l, r)
		self.propagete(plist)
		L = self.lenTreeLeaf + l
		R = self.lenTreeLeaf + r
		value = x
		while L < R:
			if R & 1:
				R -= 1
				self.lazy[R - 1] = self.func(self.lazy[R - 1], value)
				self.dat[R - 1] = self.func(self.dat[R - 1], value)
			if L & 1:
				self.lazy[L - 1] = self.func(self.lazy[L - 1], value)
				self.dat[L - 1] = self.func(self.dat[L - 1], value)
				L += 1
			L = L >> 1
			R = R >> 1
			value = self.funcRangePropagetToParent(value)
		for node in plist:
			self.dat[node] = self.func(self.dat[2 * node + 1], self.dat[2 * node + 2])

	def propagete(self, plist):
		for nodeId in plist[::-1]:
			if self.lazy[nodeId] == self.initValue:
				continue
			if nodeId < self.lenTreeLeaf - 1:
				propageteValue = self.funcPropagateToChild(self.lazy[nodeId])
				self.lazy[2 * nodeId + 1] = self.func(self.lazy[2 * nodeId + 1], propageteValue)
				self.lazy[2 * nodeId + 2] = self.func(self.lazy[2 * nodeId + 2], propageteValue)
				self.dat[2 * nodeId + 1] = self.func(self.dat[2 * nodeId + 1], propageteValue)
				self.dat[2 * nodeId + 2] = self.func(self.dat[2 * nodeId + 2], propageteValue)
			else:
				pass
			self.lazy[nodeId] = self.initValue

	def query(self, l, r):
		plist = self.nodelistFromLR(l, r)
		self.propagete(plist)
		L = self.lenTreeLeaf + l
		R = self.lenTreeLeaf + r
		view = []
		res = self.initValue
		while L < R:
			if R & 1:
				R -= 1
				res = self.func(res, self.dat[R - 1])
			if L & 1:
				res = self.func(res, self.dat[L - 1])
				L += 1
			L = L >> 1
			R = R >> 1
		return res

	def findNthValueSub(self, x, nodeId):
		if self.dat[nodeId] < x:
			return (None, x - self.dat[nodeId])
		if nodeId >= self.lenTreeLeaf - 1:
			return (True, nodeId - (self.lenTreeLeaf - 1))
		resLeft = self.findNthValueSub(x, 2 * nodeId + 1)
		if resLeft[0] != None:
			return (True, resLeft[1])
		resRight = self.findNthValueSub(resLeft[1], 2 * nodeId + 2)
		return resRight

	def findNthValue(self, x):
		return self.findNthValueSub(x, 0)[1]

class segmentTreeSum(segmentTree):

	def __init__(self):
		self.func = lambda x, y: x + y
		self.funcPropagateToChild = lambda parentValue: parentValue >> 1
		self.funcRangePropagetToParent = lambda currentValue: currentValue << 1
		self.initValue = 0

class segmentTreeMin(segmentTree):

	def __init__(self):
		self.func = lambda x, y: min(x, y)
		self.funcPropagateToChild = lambda parentValue: parentValue
		self.funcRangePropagetToParent = lambda currentValue: currentValue
		self.initValue = 2 * 10 ** 9
import sys
import sys

def do():
	st = segmentTreeSum()
	(n, t) = map(int, input().split())
	dat = list(map(int, input().split()))
	dattotal = []
	total = 0
	segtreeList = [0] * (200000 + 10)
	zatsu = set()
	for x in dat:
		total += x
		dattotal.append(total)
		zatsu.add(total)
	zatsu = list(zatsu)
	zatsu.sort()
	zatsuTable = dict()
	zatsuTableRev = dict()
	for (ind, val) in enumerate(zatsu):
		zatsuTable[val] = ind
		zatsuTableRev[ind] = val
	buf = []
	for x in dattotal:
		buf.append(zatsuTable[x])
		segtreeList[zatsuTable[x]] += 1
	st.load(segtreeList)
	from bisect import bisect_left, bisect_right
	offset = 0
	res = 0
	for i in range(n):
		x = dattotal[i]
		curvalind = zatsuTable[x]
		targetval = t + offset
		targetind = bisect_left(zatsu, targetval)
		cnt = st.query(0, targetind)
		res += cnt
		st.addValue(curvalind, -1)
		offset += dat[i]
	print(res)
do()


class SortedList:

	def __init__(self, iterable=None, _load=200):
		if iterable is None:
			iterable = []
		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))
(n, t) = map(int, input().split())
a = [int(x) for x in input().split()]
for i in range(1, n):
	a[i] += a[i - 1]
s = SortedList([0])
an = 0
t -= 1
for i in range(n):
	s.add(-a[i])
	an += s.bisect_right(t - a[i])
print(an - (n if t >= 0 else 0))


def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

def calc(prefix, t):
	ind = [i for i in range(len(prefix))]
	ind = sort_list(ind, prefix)
	prefix.sort()
	a = [0] * len(prefix)
	s = SegmentTree(a)
	j = 0
	ans = 0
	for i in range(len(prefix)):
		if j == len(prefix):
			ans += s.query(ind[i] + 1, len(prefix) - 1)
			continue
		while prefix[j] - t < prefix[i]:
			s.__setitem__(ind[j], 1)
			j += 1
			if j == len(prefix):
				break
		ans += s.query(ind[i] + 1, len(prefix) - 1)
	print(ans)
(n, t) = map(int, input().split())
l = list(map(int, input().split()))
pre = [0]
for i in range(n):
	pre.append(pre[-1] + l[i])
calc(pre, t)


def lowbit(index):
	return index & -index

def update(index, delta=1):
	while index <= size:
		tree[index] += delta
		index += lowbit(index)

def query(index):
	res = 0
	while index > 0:
		res += tree[index]
		index -= lowbit(index)
	return res
(n, t) = list(map(int, input().split()))
a = list(map(int, input().split()))
summ_raw = [0]
summ_minus = []
cur = 0
for i in range(n):
	cur += a[i]
	summ_raw.append(cur)
	summ_minus.append(cur - t)
summ = sorted(list(set(summ_raw + summ_minus)))
size = len(summ)
d = {}
for i in range(size):
	d[summ[i]] = i + 1
tree = [0] * (size + 1)
update(d[0])
res = 0
for i in range(1, n + 1):
	v = summ_raw[i]
	index = d[v - t]
	cur = query(size) - query(index)
	res += cur
	update(d[v])
print(res)


from bisect import bisect_left
sum = [0] * 200005
srt = []
(n, t) = list(map(int, input().split()))
a = list(map(int, input().split()))
tree = [0] * 200005

def get(x):
	ans = 0
	while x:
		ans += tree[x]
		x -= x & -x
	return ans

def update(x):
	while x <= 200002:
		tree[x] += 1
		x += x & -x
for i in range(n):
	if i:
		sum[i] = sum[i - 1] + a[i]
	else:
		sum[i] = a[i]
	srt.append(sum[i])
if 0 not in srt:
	srt.append(0)
srt.sort()
ans = 0
update(bisect_left(srt, 0) + 1)
for i in range(n):
	l = min(len(srt) - 1, bisect_left(srt, sum[i] - t))
	if srt[l] <= sum[i] - t:
		l = l + 1
	cnt = get(l)
	ans += i + 1 - cnt
	update(bisect_left(srt, sum[i]) + 1)
print(ans)


r = input
(n, t) = map(int, r().split())
arr = [int(x) for x in r().split()]
N = -40 ** 14 - 20 ** 14
presum = [0]

def update(Bit, x):
	while x <= n:
		Bit[x] += 1
		x += x & -x

def get(Bit, x):
	res = 0
	while x > 0:
		res += Bit[x]
		x -= x & -x
	return res
for i in arr:
	presum.append(presum[-1] + i)
fakeIndex = [N]
for i in presum:
	fakeIndex.append(i)
	fakeIndex.append(i - t)
fakeIndex.sort()
Indx = {}
for (i, j) in enumerate(fakeIndex):
	Indx[j] = i
n = len(fakeIndex)
Bit = [0 for i in range(0, n + 1)]
ans = 0
cnt = 0
for i in presum:
	ans += cnt - get(Bit, Indx[i - t])
	update(Bit, Indx[i])
	cnt += 1
print(ans)


(n, t) = list(map(int, input().split()))
a = list(map(int, input().split()))
summ = [0]
cur = 0
for i in range(n):
	cur += a[i]
	summ.append(cur)

def merge(l, mid, r):
	(i, j) = (l, mid + 1)
	ans = 0
	while i <= mid and j <= r:
		if summ[i] + t > summ[j]:
			ans += mid + 1 - i
			j += 1
		else:
			i += 1
	tmp = []
	(i, j) = (l, mid + 1)
	while i <= mid and j <= r:
		if summ[i] <= summ[j]:
			tmp.append(summ[i])
			i += 1
		else:
			tmp.append(summ[j])
			j += 1
	if i <= mid:
		tmp.extend(summ[i:mid + 1])
	if j <= r:
		tmp.extend(summ[j:r + 1])
	for i in range(l, r + 1):
		summ[i] = tmp[i - l]
	return ans

def helper(l, r):
	if l == r:
		return 0
	mid = (l + r) // 2
	ans1 = helper(l, mid)
	ans2 = helper(mid + 1, r)
	ans3 = merge(l, mid, r)
	return ans1 + ans2 + ans3
res = helper(0, n)
print(res)


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
import bisect
from collections import Counter
import bisect
from collections import deque

def up(ind, val):
	while ind <= cnt + 1:
		bit[ind] += 1
		ind += ind & -ind

def bit_sum(ind):
	val = 0
	while ind > 0:
		val += bit[ind]
		ind -= ind & -ind
	return val
(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
p = [0] * n
p[0] = arr[0]
minus = [arr[0] - k]
for i in range(1, n):
	p[i] = p[i - 1] + arr[i]
	minus.append(p[i] - k)
minus.extend(p)
array = sorted(minus)
cnt = 1
d = {}
for i in array:
	if i not in d:
		d[i] = cnt
		cnt += 1
bit = [0] * (cnt + 2)
ans = 0
for i in p:
	var = d[i - k]
	ans += bit_sum(cnt + 1) - bit_sum(var)
	up(d[i], 1)
	if i < k:
		ans += 1
print(ans)


from itertools import accumulate

class binary_index_tree(object):

	def __init__(self, n):
		self.bit = [0] * n
		self.n = n

	def add(self, ind, num):
		while ind <= self.n:
			self.bit[ind - 1] += num
			ind += ind & -ind

	def sum(self, ind):
		ret = 0
		while ind > 0:
			ret += self.bit[ind - 1]
			ind -= ind & -ind
		return ret

	def sum_from(self, from_, to_):
		return self.sum(to_) - self.sum(from_)
(n, t) = map(int, input().split())
a = list(map(int, input().split()))
sa = list(accumulate(a))
ss = sa + [i - t for i in sa]
ss.sort()
d = {}
cnt = 0
for i in sorted(ss):
	if i not in d:
		d[i] = cnt
		cnt += 1
BIT = binary_index_tree(cnt + 1)
ans = 0
for ar in sa:
	r = d[ar - t] + 1
	i = d[ar] + 1
	ans += BIT.sum_from(r, cnt + 1)
	BIT.add(i, 1)
for i in sa:
	if i < t:
		ans += 1
print(ans)


import sys
import bisect
input = sys.stdin.readline

class Bit:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

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

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i
(n, t) = map(int, input().split())
a = list(map(int, input().split()))
pre = [0] * (n + 1)
for i in range(n):
	pre[i + 1] = pre[i] + a[i]
pre.sort(reverse=True)
upsum = [-10 ** 18]
for i in range(n + 1):
	if i == 0 or pre[i] != pre[i - 1]:
		upsum.append(pre[i])
upsum.sort(reverse=True)

def lower(i):
	l = 0
	r = len(upsum)
	while r - l > 0:
		m = (l + r) // 2
		if upsum[m] <= i:
			r = m
		else:
			l = m + 1
	return l
ans = 0
cur = 0
BIT = Bit(n + 2)
BIT.add(lower(0) + 1, 1)
for aa in a:
	cur += aa
	ans += BIT.sum(lower(cur - t))
	BIT.add(lower(cur) + 1, 1)
print(ans)


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 merge(l, r):
	if l >= r:
		return
	global res
	mid = (l + r) // 2
	merge(l, mid)
	merge(mid + 1, r)
	j = mid + 1
	i = l
	while i <= mid:
		while j <= r:
			if a[j] < m + a[i]:
				j += 1
			else:
				break
		res += j - mid - 1
		i += 1
	a[l:r + 1] = sorted(a[l:r + 1])
	return res
(n, m) = map(int, input().split())
b = list(map(int, input().split()))
a = [0] * (n + 1)
res = 0
for i in range(1, n + 1):
	a[i] = a[i - 1] + b[i - 1]
print(merge(0, n))


from collections import defaultdict
import bisect
(n, t) = map(int, input().split())
di = list(map(int, input().split()))
ai = [di[0]]
for i in range(1, n):
	ai.append(ai[-1] + di[i])
mapp = defaultdict(int)
ais = list(sorted(ai))
ind = 0
for i in range(n):
	if not mapp[ais[i]]:
		mapp[ais[i]] = ind
		ind += 1
li = [-1] * n
for i in range(n):
	li[i] = mapp[ai[i]]
BIT = [0] * (n + 1)

def getsum(BITTree, i):
	s = 0
	i = i + 1
	while i > 0:
		s += BITTree[i]
		i -= i & -i
	return s

def updatebit(BITTree, n, i, v):
	i += 1
	while i <= n:
		BITTree[i] += v
		i += i & -i
i = 0
ans = 0
while i < n:
	diff = ai[i] - t
	ind = bisect.bisect_right(ais, diff)
	if ai[i] < t:
		ans += 1
	if ind != n:
		val = mapp[ais[ind]]
		ans += getsum(BIT, n - 1) - getsum(BIT, val - 1)
	updatebit(BIT, n, li[i], 1)
	i += 1
print(ans)