Description

Young Mirko has recently been buying Voodoo dolls. Since he is interested in the cheapest things, he tracks the prices of Voodoo dolls every day. He already knows the prices over the last $N$ days, where the price on day $i$ is denoted by $a_i$.

Mirko believes that there is some connection between the average price over several consecutive days and the price on the next day. He wants to verify his idea, but he is stuck on a problem: “For a given $P$, how many different contiguous subarrays within these $N$ days have an average price greater than or equal to $P$?”

Two contiguous subarrays are different if and only if their starting positions or ending positions are different.

Input Format

The first line contains an integer $N$.

The next line contains $N$ integers, where the $i$-th integer represents $a_i$.

The last line contains an integer $P$.

Output Format

Output one integer on a single line, representing how many different contiguous subarrays within these $N$ days have an average price greater than or equal to $P$.

3
1 2 3
3

1

3
1 3 2
2

5

3
1 3 2
3

1

Hint

[Sample 1 Explanation]

There are only 3 subarrays whose average is greater than or equal to 3.

[Sample 2 Explanation]

There are 5 subarrays whose average is greater than or equal to 2, and they are:

1 3

1 3 2

3

3 2

2

[Constraints]

For $30\%$ of the testdata, $1 \le N \le 10^4$.

For $100\%$ of the testdata, $1 \le N \le 10^6$, $1 \le a_i \le 10^9$, $1 \le P \le 10^9$.

[Notes]

The scoring for this problem follows the original problem, with a full score of $140$.

Translated from COCI 2015-2016 CONTEST #2 T5 VUDU.

Translated by ChatGPT 5