D - Enough Array

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400

問題文

長さ N の正整数列 A=a_1,a_2,…,a_{N} と整数 K が与えられます。A の連続する部分列であって、以下の条件を満たすようなものは何個あるでしょうか。

  • (条件) 連続部分列に含まれる全ての要素の値の和は、K 以上である。

ただし、ある二つの連続部分列が列として同じでも、取り出された位置が異なるならそれらは別々に数えるものとします。

出力が 32bit 整数型に収まらない場合があることに注意してください。

制約

  • 1 \leqq a_i \leqq 10^5
  • 1 \leqq N \leqq 10^5
  • 1 \leqq K \leqq 10^{10}

入力

入力は以下の形式で標準入力から与えられます。

N K
a_1 a_2 ... a_N

出力

条件を満たすような連続部分列の個数を出力してください。


入力例 1

4 10
6 1 2 7

出力例 1

2
  • A[1..4]=a_1,a_2,a_3,a_4 (要素の値の和は 16)
  • A[2..4]=a_2,a_3,a_4 (要素の値の和は 10)

の二通りです。


入力例 2

3 5
3 3 3

出力例 2

3

ある二つの連続部分列が列として同じでも、取り出された位置が異なるならそれらは別々に数えることに注意してください。


入力例 3

10 53462
103 35322 232 342 21099 90000 18843 9010 35221 19352

出力例 3

36

Score : 400 points

Problem Statement

You are given a sequence of positive integers of length N, A=a_1,a_2,…,a_{N}, and an integer K. How many contiguous subsequences of A satisfy the following condition?

  • (Condition) The sum of the elements in the contiguous subsequence is at least K.

We consider two contiguous subsequences different if they derive from different positions in A, even if they are the same in content.

Note that the answer may not fit into a 32-bit integer type.

Constraints

  • 1 \leq a_i \leq 10^5
  • 1 \leq N \leq 10^5
  • 1 \leq K \leq 10^{10}

Input

Input is given from Standard Input in the following format:

N K
a_1 a_2 ... a_N

Output

Print the number of contiguous subsequences of A that satisfy the condition.


Sample Input 1

4 10
6 1 2 7

Sample Output 1

2

The following two contiguous subsequences satisfy the condition:

  • A[1..4]=a_1,a_2,a_3,a_4, with the sum of 16
  • A[2..4]=a_2,a_3,a_4, with the sum of 10

Sample Input 2

3 5
3 3 3

Sample Output 2

3

Note again that we consider two contiguous subsequences different if they derive from different positions, even if they are the same in content.


Sample Input 3

10 53462
103 35322 232 342 21099 90000 18843 9010 35221 19352

Sample Output 3

36