T2 合法子段（window）

题目描述

给定一个长度为 $n$ 的正整数序列 $a_1,a_2,\dots,a_n$（从 $1$ 开始编号）和一个上界 $S$。我们称一个连续子段 $a_l,a_{l+1},\dots,a_r$（$1\le l\le r\le n$）是合法的，当且仅当

请你统计该序列中一共有多少个合法的连续子段。

输入文件 window.in，输出文件 window.out。

输入格式

输入共两行。

第一行包含两个正整数 $n,S$，分别表示序列长度与和的上界。

第二行包含 $n$ 个正整数 $a_1,a_2,\dots,a_n$。

输出格式

输出共一行，包含一个整数，表示合法连续子段的数量。

样例 1 输入

5 8
1 3 2 5 4

样例 1 输出

9

样例 1 解释

所有和不超过 $8$ 的连续子段为：

$[1]$、$[1,3]$、$[1,3,2]$、$[3]$、$[3,2]$、$[2]$、$[2,5]$、$[5]$、$[4]$，共 $9$ 个。

例如 $[5,4]$ 的和为 $9>8$，不合法。

样例 2 输入

10 20
1400 8353 3947 940 230 9936 6271 6156 2775 5926

样例 2 输出

0

样例 2 解释

最小的元素也已经是 $230>20$，因此没有任何非空连续子段的和不超过 $S$。

数据规模与约定

• 对于 $30\%$ 的数据，保证 $n\le 1000$。
• 对于另 $30\%$ 的数据，保证 $n\le 10^5$。
• 对于 $100\%$ 的数据，保证 $1\le n\le 2\times 10^5$，$1\le a_i\le 10^4$，$1\le S\le 10^9$。