{"raw_statement":[{"iden":"problem statement","content":"You are given a positive integer $S$. For a sequence of positive integers $x$, we define $f(x)$ as follows:\n\n*   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)$.\n\nIt can be proved that the value of $f$ is always definable under the constraints of this problem.\nYou 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))$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 250000$\n*   $1 \\leq S \\leq 10^{15}$\n*   $1 \\leq A_i \\leq \\min(S,10^9)$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $S$\n$A_1$ $A_2$ $\\cdots$ $A_N$"},{"iden":"sample input 1","content":"3 3\n1 2 3"},{"iden":"sample output 1","content":"8\n\nFor example, consider $x=(1,2,3)$. The decomposition $(1,2),(3)$ satisfies the condition, and no decomposition into fewer than two contiguous subsequences satisfies the condition, so $f((1,2,3))=2$.\nShown below are the possible $l,r$ and the corresponding values of $f$:\n\n*   $(l,r)=(1,1)$: $f((1))=1$\n*   $(l,r)=(1,2)$: $f((1,2))=1$\n*   $(l,r)=(1,3)$: $f((1,2,3))=2$\n*   $(l,r)=(2,2)$: $f((2))=1$\n*   $(l,r)=(2,3)$: $f((2,3))=2$\n*   $(l,r)=(3,3)$: $f((3))=1$\n\nThus, the answer is $1+1+2+1+2+1=8$."},{"iden":"sample input 2","content":"5 1\n1 1 1 1 1"},{"iden":"sample output 2","content":"35"},{"iden":"sample input 3","content":"5 15\n5 4 3 2 1"},{"iden":"sample output 3","content":"15"},{"iden":"sample input 4","content":"20 1625597454\n786820955 250480341 710671229 946667801 19271059 404902145 251317818 22712439 520643153 344670307 274195604 561032101 140039457 543856068 521915711 857077284 499774361 419370025 744280520 249168130"},{"iden":"sample output 4","content":"588"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}