题目描述

年轻的 Mirko 最近一直在买 Voodoo 娃娃。因为他对最便宜的东西很感兴趣，所以他每天都在追踪 Voodoo 娃娃的价格。他已经得知了最近 $N$ 天的娃娃价格，第 $i$ 天的娃娃价格记为 $a_i$。

Mirko 认为，连续几天的娃娃平均价格与下一天的娃娃价格之间存在某种联系。他想验证自己的观点，却被一个问题难倒了：“对于一个给定的 $P$，在这 $N$ 天内有多少个不同的连续子序列令娃娃的平均价格大于或等于 $P$ ？”

两个连续子序列不同当且仅它们的开始位置或结束位置不同。

输入格式

第一行一个整数 $N$。

接下来一行有 $N$ 个整数，第 $i$ 个整数表示 $a_i$。

最后一行有一个整数 $P$。

输出格式

一行一个整数，表示在这 $N$ 天内有多少个不同的连续子序列令娃娃的平均价格大于或等于 $P$。

3
1 2 3
3

1

3
1 3 2
2

5

3
1 3 2
3

1

提示

【样例 1 解释】

平均数大于等于 3 的子序列只有 3。

【样例 2 解释】

平均数大于等于 2 的子序列有 5 个，它们是：

1 3

1 3 2

3

3 2

2

【数据范围】

对于 $30\%$ 的数据，$1\le N\le 10^4$；

对于 $100\%$ 的数据，$1\le N\le 10^6，1\le a_i\le 10^9，1\le P\le 10^9$。

【说明】

本题数据点得分依原题，满分 140。

题目译自 COCI 2015-2016 CONTEST #2 T5 VUDU。