AT_arc169_b [ARC169B] Subsegments with Small Sums

[problemUrl]: https://atcoder.jp/contests/arc169/tasks/arc169_b 正整数 $ S $ が与えられます． 正整数列 $ x $ に対し，$ f(x) $ を以下のように定めます． - $ x $ をいくつかの連続部分列に分解することを考える． このとき，どの連続部分列についても要素の総和が $ S $ **以下**でなくてはならない． このような分解における連続部分列の個数の最小値を $ f(x) $ の値とする． なお，この問題の制約下では $ f $ の値が必ず定義できることが証明できます． 正整数列 $ 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 $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $

答えを出力せよ．

### 制約 - $ 1\ \leq\ N\ \leq\ 250000 $ - $ 1\ \leq\ S\ \leq\ 10^{15} $ - $ 1\ \leq\ A_i\ \leq\ \min(S,10^9) $ - 入力される値はすべて整数． ### Sample Explanation 1 例えば $ x=(1,2,3) $ を考えると，$ (1,2),(3) $ という分解が条件を満たし， かつ $ 2 $ 個未満の連続部分列に分解した場合は条件を満たさないため，$ 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 $ になります．