Problem Description

Young Mirko has been buying Voodoo dolls recently. Because he is very interested in the cheapest items, he tracks the prices of Voodoo dolls every day. He has learned the prices of dolls for the past $N$ days, with the price on the $i$-th day denoted as $a_i$.

Mirko believes that there is a certain connection between the average price of dolls over several consecutive days and the price of dolls on the following day. He wants to verify his theory but is stumped by a question: "For a given $P$, how many different continuous subsequences within these $N$ days have an average price greater than or equal to $P$?"

Two continuous subsequences are considered different if and only if their starting 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 a single integer, which represents the number of different continuous subsequences within these $N$ days that have an average price greater than or equal to $P$.

Sample Input and Output

Sample Input #1

3
1 2 3
3

Sample Output #1

1

Sample Input #2

3
1 3 2
2

Sample Output #2

5

Sample Input #3

3
1 3 2
3

Sample Output #3

1

Notes/Hints

[Sample 1 Explanation]

The only subsequence with an average greater than or equal to 3 is 3.

[Sample 2 Explanation]

There are 5 subsequences with an average greater than or equal to 2, which are:

1 3

1 3 2

3

3 2

2

[Data Range]

For $30\%$ of the data, $1 \le N \le 10^4$;

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

[Note]

This problem's scoring is based on the original contest, with a full score of 140.

This problem is translated from COCI 2015-2016 CONTEST #2 T5 VUDU.

见题面 Input 部分

见题面 Output 部分