题目描述

给定一个长度为\(n\)的正整数序列\(h_1,h_2 \cdots h_n\)以及一个阈值\(k\)，输出有多少个非空区间满足其中元素的平均值\(\ge k\)。这里“区间”指的是从原序列中截取下标连续的一段（包括单个元素以及原序列自身）。

输入格式

第一行两个整数\(n,k\)；
第二行\(n\)个正整数\(h_1,h_2 \cdots h_n\)。

输出格式

一个非负整数，表示符合要求的区间数量。

样例

输入

3 6
7 5 7

输出

5

样例说明

样例中满足条件的区间共有5个：
\(\{h_1\}\)，均值为7；
\(\{h_1, h_2\}\)，均值为6；
\(\{h_1, h_2, h_3\}\)，均值为19/3；
\(\{h_2, h_3\}\)，均值为6；
\(\{h_3\}\)，均值为7。

数据规模、时空限制

对于20%的数据，\(n \le 100\)
对于40%的数据，\(n \le 1000\)
对于100%的数据，\(n \le 10^5, \quad 1 \le k,h_i \le 10^9\)
时间限制1s，空间限制512MB。

来源

2019.2 TYWZ提高组集训
供题人：于剑