某公司正在统计一段时间内的日常支出情况。共有连续的 N 天,第 i 天的支出金额为 Ai(均为正整数)。
财务部门希望分析:在所有连续若干天构成的区间时间段中,有多少个区间时间段的总支出金额不少于给定的预算下限 K。
具体地,若一个区间从第 l 天开始,到第 r 天结束(1≤l≤r≤N),其总支出为
。你需要计算满足 S≥K 的不同区间 l,r 的总数。
需要注意的是:
注意:只要两个区间的开始位置 l 或结束位置 r 不同,即视为不同的区间。
请你帮助财务部门计算满足条件的区间时间段数量。
第一行输入正整数 N 和正整数 K。
第二行包含 N 个正整数:A1,A2,…,AN,表示每天的支出金额,相邻两数之间用一个空格隔开。
输出一个整数,表示满足总支出不少于 K 的连续区间时间段数量。
4 10 6 1 2 7
2
3 5 3 3 3
3
10 53462 103 35322 232 342 21099 90000 18843 9010 35221 19352
36
样例 1 说明
满足条件的区间共有 2 个:
1.[1,4]:支出总额为 6+1+2+7=16≥10。
2.[2,4]:支出总额为 1+2+7=10≥10。
数据范围

对于 100% 的数据满足,1≤N≤10^5,1≤Ai≤10^5,1≤K≤10^10。
| 时间限制 | 1 秒 |
| 内存限制 | 128 MB |