P7868 [COCI 2015/2016 #2] VUDU

Young Mirko has been buying voodoo dolls lately. Considering that he is very interested in the cheapest purchase possible, he has been tracking the prices of voodoo dolls each day.His price list consists of doll prices in the last $N$ days, where doll price $a_i$ represents the price of a doll $i$ days ago. Mirko thinks he has noticed a connection between the average doll price in a sequence of **consecutive** days and the price on the following day. He wants to test his hunch and is puzzled by a very interesting question: "For a given $P$, how many different consecutive subsequences in the last $N$ days are there, when the **average** doll price was greater than or equal to $P$?" Two consecutive subsequences are considered different if their beginnings or ends are different.

The first line of input contains the integer $N$, the sequence length. The second line of input contains $N$ prices $a_i$. The third line of input contains an integer $P$.

The first and only line of output must contain the answer to Mirko's question for a given $P$.

### Clarification of the first example The only subsequence that has an average greater than or equal to $3$ is $\lbrace 3 \rbrace$. ### Clarification of the second example The subsequences that have an average greater than or equal to $2$ are $\lbrace 1, 3 \rbrace$, $\lbrace 1, 3, 2 \rbrace$, $\lbrace 3 \rbrace$, $\lbrace 3 ,2 \rbrace$, $\lbrace 2 \rbrace$. ### Scoring In test cases worth $30\%$ of the points, $1\le N \le 10^4$. In test cases for all points, $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$. From [COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [CONTEST #2](https://hsin.hr/coci/archive/2015_2016/contest2_tasks.pdf) **T5 VUDU**. Organized by @[xiewendongTony](/user/1074137).