AdditionalFile3735.zip

#3735. 「COCI 2015.11」VUDU

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

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

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

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

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

输入格式

第一行一个整数 $N$。

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

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

输出格式

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

样例 1

输入

3
1 2 3
3

输出

1

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

样例 2

输入

3
1 3 2
2

输出

5

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

1. 1 3
2. 1 3 2
3. 3
4. 3 2
5. 2

样例 3

输入

3
1 3 2
3

输出

1

数据范围与提示

• 对于 $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$。