#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## Problem Description

Recently, Damian discovered an old camera lying around his house. Curious, he decides to take it out for a spin and go around phototaking.

On the streets, he spots a collection of *N* assorted items on display in a row at a museum's window. He then evaluates each item and assigns them each an awesomeness index *A _{i}*.

He decides to take photographs of the collection of items. Obviously, he can only take photos of contiguous ranges of items.

However, he prefers to take ordinary photos. Thus, he wants to know how many (contiguous) ranges exist such that the sum of the awesomeness indices of the elements in the range is no larger than a threshold *S*.

## Input

The first line contains two integers, *N* and *S*, the number of items and the threshold.

The second line contains *N* space-separated integers, with the *i*th integer representing the awesomeness index of the *i*th item.

## Output

The output should contain one line containing one integer, the number of ranges that sum up to no larger than the threshold.

## Limits

For all subtasks, 0 ≤ Ai ≤ 10^{6}.

Subtask 1 (7%): 1 ≤ N ≤ 10^{6}; *S* = 10^{12}.

Subtask 2 (11%): 1 ≤ N ≤ 500; 0 ≤ S ≤ 10^{8}.

Subtask 3 (13%): 1 ≤ N ≤ 10 000; 0 ≤ S ≤ 10^{8}.

Subtask 4 (47%): 1 ≤ N ≤ 10^{5}; 0 ≤ S ≤ 10^{8}.

Subtask 5 (23%): 1 ≤ N ≤ 10^{7}; 0 ≤ S ≤ 10^{8}.

Subtask 6 (0%): Sample Testcases.

## Sample Testcase 1

### Input

5 4 0 3 1 2 4

### Output

9

## Sample Output 1 Explanation

The ranges are {0}, {3}, {1}, {2}, {4}, {0, 3}, {3, 1}, {1, 2} and {0, 3, 1}.

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 7 | 6 | 0.9s | 256MB | Minimum |

2 | 11 | 6 | 0.9s | 256MB | Minimum |

3 | 13 | 6 | 0.9s | 256MB | Minimum |

4 | 46 | 6 | 0.9s | 256MB | Minimum |

5 | 23 | 7 | 0.9s | 256MB | Minimum |

6 | 0 | 1 | 0.9s | 256MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o phototaking -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512