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$

Difficulty: interview

Starter code:

Solutions:
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=list(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)

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



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 = set([s for s in S] + [s - t for s in S])
    T = sorted(T)
    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))



r = input
n,t = map(int,r().split())
arr = [int(x) for x in r().split()]
N = -40**14-20**14
presum =[0]
#Function
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):
    #print(j,' ',i)
    Indx[j] = i
n = len(fakeIndex)
Bit = [0 for i in range(0,n+1)]
ans = 0
cnt = 0
for i in presum:
    #temp = get(Bit,Indx[i-t])
    ans+=(cnt - get(Bit,Indx[i-t]))
    update(Bit,Indx[i])
    cnt+=1
print(ans)

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)



# import atexit
# import io
# import sys
#
# _INPUT_LINES = sys.stdin.read().splitlines()
# input = iter(_INPUT_LINES).__next__
# _OUTPUT_BUFFER = io.StringIO()
# sys.stdout = _OUTPUT_BUFFER
#
#
# @atexit.register
# def write():
#     sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())

from bisect import bisect_left
from itertools import accumulate


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


def query(x):
    ans = 0
    while x > 0:
        ans += bit[x]
        x -= x & (-x)
    return ans


n, t = list(map(int, input().split()))
arr = list(accumulate(list(map(int, input().split()))))

bit = [0 for i in range(n + 2)]

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(lower_idx - 1) - 1
    update(leftmost[arr[i]], 1)

print(res)


# -*- coding:utf-8 -*-

"""

created by shuangquan.huang at 11/21/18


Fenwick Tree

prefix sum in s
j < i, s[i]-s[j] < t,

i+1 - (c = count of j that makes s[i]-s[j] >= t)
c = count of s[j] <= s[i] - t


"""
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)





# https://codeforces.com/contest/1042/problem/D
# 解説AC
# sr - sl < t
# sl > sr - t
# index - sr -t 以下の数

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):
        # index is one_indexed
        while(ind <= self.n):
            self.bit[ind - 1] += num
            ind += ind & -ind
    # [1, ind)
    def sum(self, ind):
        # index is one indexed
        ret = 0
        while(ind > 0):
            ret += self.bit[ind-1]
            ind -= ind & -ind
        return ret
    # [from_, to_)
    def sum_from(self, from_, to_):
        # index is one indexed
        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]
#print(ss)
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:
    # 1-indexed
    r = d[ar-t] + 1
    i = d[ar] + 1
    ans += BIT.sum_from(r, cnt+1)
    BIT.add(i, 1)
#print(ans)
for i in sa:
    if i < t:
        ans += 1
print(ans)

def merge(l,r):
    nonlocal 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)

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)
    #print(ans1, ans2, ans3)
    return ans1 + ans2 + ans3

res = helper(0, n)
print(res)


'''
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
'''


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()))
#n, t = 5, 4
#a = [5, -1, 3, 4, -1]

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
#print(summ)
#print(d)
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))
    #print(tree, size, query(size), cur, v, index)
    res += cur
    update(d[v])
print(res)



'''
# divide and conquer, two pointers

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)
    #print(ans1, ans2, ans3)
    return ans1 + ans2 + ans3

res = helper(0, n)
print(res)
'''

'''
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
'''



n,t=list(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 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):
        """initialize the segment tree with data"""
        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)
            #print(ans,ind[i])
            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,ind[i])
    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)

#yeh dil maange more
def merge(l,r):
    nonlocal 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)

def merge(l,r):
    nonlocal 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)