Problem Statement

You are given a positive integer $S$. For a sequence of positive integers $x$, we define $f(x)$ as follows:

• Consider decomposing $x$ into several contiguous subsequences. For each contiguous subsequence, the sum of its elements must be at most $S$. The minimum number of contiguous subsequences in such a decomposition is the value of $f(x)$.

It can be proved that the value of $f$ is always definable under the constraints of this problem.

You are given a sequence of positive integers $A=(A_1,A_2,\cdots,A_N)$. Find the value of $\sum_{1 \leq l \leq r \leq N} f((A_l,A_{l+1},\cdots,A_r))$.

Constraints

• $1 \leq N \leq 250000$
• $1 \leq S \leq 10^{15}$
• $1 \leq A_i \leq \min(S,10^9)$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N S
A_1 A_2 \cdots A_N

Output

Print the answer.