Given an array of \(n\) integers \(a_i\). Let's say that the segment of this array \(a[l..r] (1≤l≤r≤n)\) is good if the sum of elements on this segment is at most \(s\). Your task is to find the number of good segments.

Input

• The first line contains integers \(n\) and \(s\) \((1≤n≤10^5, 1≤s≤10^{18})\).
• The second line contains integers \(a_i (1≤a_i≤10^9)\).

Output

• The number of good segments.

Example

Input

7 20
2 6 4 3 6 8 9

Output

19

Nguồn: Codeforces