AT_arc169_b [ARC169B] Subsegments with Small Sums

给定一个正整数 $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 \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$。