Average Voodoo Doll Price

Time limit2sMemory limit64 MB

Summary

Count the contiguous runs of days whose average doll price is at least P.

Level: Medium6 of 10
Topics: Prefix sum, Divide and conquer, Sorting
Solved: No attempts yet

Problem

Mirko has been buying voodoo dolls. He wants to buy as cheaply as possible, so he writes down the price of a doll every day. His price list holds the doll prices of the last $N$ days, and the price $a_i$ is the price of a doll $i$ days ago.

Mirko thinks the average price over a run of consecutive days is connected to the price on the next day. While testing that hunch he ran into another question. For a given $P$ , how many runs of consecutive days within the last $N$ days had an average doll price greater than or equal to $P$ ?

Two runs of consecutive days count as different when they start at different positions or end at different positions.

Input

The first line contains the sequence length $N$ . ( $1 \le N \le 1\,000\,000$ )

The second line contains the $N$ prices $a_i$ . ( $0 \le a_i \le 1\,000\,000\,000$ )

The third line contains an integer $P$ . ( $0 \le P \le 1\,000\,000\,000$ )

Output

Print on the first line the number of consecutive runs whose average price is greater than or equal to $P$ .

Hint

In the first example the only run whose average is at least 3 is {3}.

In the second example the runs whose average is at least 2 are {1, 3}, {1, 3, 2}, {3}, {3, 2}, {2}.

Examples3

Example 1
Input
```
3
1 2 3
3
```
Expected output
```
1
```
Example 2
Input
```
3
1 3 2
2
```
Expected output
```
5
```
Example 3
Input
```
3
1 3 2
3
```
Expected output
```
1
```