题目描述

给定一个正整数 $S$。对于正整数序列 $x$ ，我们定义函数 $f(x)$ 如下:

• 将 $x$ 分解为几个连续的子序列。对于每个连续子序列，其元素之和最多为 $S$。$f(x)$ 是在这样的要求下分解成的连续子序列的最小数目。

现在给定一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\cdots,A_N)$，请求出 $\sum\_{1 \leq l \leq r \leq N} f((A\_l,A\_{l+1},\cdots,A\_r))$。

输入格式

第一行两个整数 $N$ 和 $S$。

第二行 $N$ 个整数表示序列 $A$。

输出格式

一行一个整数 $\sum\_{1 \leq l \leq r \leq N} f((A\_l,A\_{l+1},\cdots,A\_r))$。

样例 1

输入

3 3
1 2 3

输出

8

样例 2

输入

5 1
1 1 1 1 1

输出

35

样例 3

输入

5 15
5 4 3 2 1

输出

15

样例 4

输入

20 1625597454
786820955 250480341 710671229 946667801 19271059 404902145 251317818 22712439 520643153 344670307 274195604 561032101 140039457 543856068 521915711 857077284 499774361 419370025 744280520 249168130

输出

588

说明/提示

$1 \leq N \leq 250000$，$1 \leq S \leq 10^{15}$，$1 \leq A_i \leq \min(S,10^9)$，所有输入都是整数。

样例一解释：

样例中 $x=(1,2,3)$。分解方案 $(1,2),(3)$ 满足条件，可以证明没有分解成少于两个连续子序列的方案满足条件，所以 $f((1,2,3))=2$。

下面显示的是可能的 $l,r$ 和对应的 $f$ 值:

• $(l,r)=(1,1)$：$f((1))=1$
• $(l,r)=(1,2)$：$f((1,2))=1$
• $(l,r)=(1,3)$：$f((1,2,3))=2$
• $(l,r)=(2,2)$：$f((2))=1$
• $(l,r)=(2,3)$：$f((2,3))=2$
• $(l,r)=(3,3)$：$f((3))=1$

因此，答案是$1+1+2+1+2+1=8$。