小慕正在维护一座名为「流量水晶」的数据监测系统,它每秒记录一次网络请求量,并存入数组 `requests` 中。当某个连续内的请求总量超过设定的时,系统就会触发一次 请求过载事件。 请求过载事件 定义如下: 在一个连续的时间窗口(窗口长度范围为 `[minWindow, maxWindow]`),如果该窗口内的请求量之和大于设定的阈值 `maxLoad`,则视为一次 请求过载事件。 注意: 1. 两个时间窗口只要起点或终点不同,就视为不同的时间窗口。 2. 保证请求过载事件的总次数不超过 100,000 次。 请计算小慕的系统触发了多少次请求过载事件。
提示:带虚线的词点一下有通俗解释。
输入描述
第一行输入一个整数 `n`,表示数组 `magicFlows` 的长度,满足 `1 <= n <= 100,000`。 第二行输入 `n` 个整数,表示数组 `magicFlows`,其中 `0 <= magicFlows[i] <= 10,000`。 第三行、第四行分别输入两个整数,分别表示时间窗口的最小长度 `minWindow` 和最大长度 `maxWindow`,满足 `1 <= minWindow <= maxWindow <= n`。 第五行输入一个整数 `magicThreshold`,表示魔法超载的阈值,满足 `1 <= magicThreshold <= 10^9`。
输出描述
输出一个整数,表示发生魔法超载事件的次数。
示例
示例 1
输入
5 5 2 3 6 4 2 3 10
输出
2
说明:总计 2 次魔法超载事件:[2, 3, 6], [3, 6, 4]
示例 2
输入
5 1 1 1 1 1 1 5 10
输出
0
示例 3
输入
10 10 9 8 7 6 5 4 3 2 1 2 5 15
输出
16
时间限制 1000 ms · 内存限制 128 MB