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 Ai.
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 ith integer representing the awesomeness index of the ith 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 ≤ 106.
Subtask 1 (7%): 1 ≤ N ≤ 106; S = 1012.
Subtask 2 (11%): 1 ≤ N ≤ 500; 0 ≤ S ≤ 108.
Subtask 3 (13%): 1 ≤ N ≤ 10 000; 0 ≤ S ≤ 108.
Subtask 4 (47%): 1 ≤ N ≤ 105; 0 ≤ S ≤ 108.
Subtask 5 (23%): 1 ≤ N ≤ 107; 0 ≤ S ≤ 108.
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}.