Subarray Average Threshold

Mirko has been tracking the price of Voodoo dolls over the past N days. On day i, the doll price is given as \(a_i\). He believes there is a correlation between the average price of dolls over a continuous sequence of days and the doll price on the following day. To test his theory, he wants to answer the following question:

For a given threshold \(P\), how many distinct continuous subarrays (contiguous segments) among the N days have an average price that is greater than or equal to \(P\)?

A continuous subarray is defined by its start and end indices. Two subarrays are considered different if their start or end indices differ.

Note: The average of a subarray \(a_l, a_{l+1}, \dots, a_r\) is defined as \(\frac{a_l+a_{l+1}+\cdots+a_r}{r-l+1}\). This condition \(\frac{a_l+\cdots+a_r}{r-l+1} \ge P\) can be rewritten (after multiplying both sides by \(r-l+1\)) as \(a_l+\cdots+a_r \ge P\,(r-l+1)\). It is often useful to subtract \(P\) from each \(a_i\) and count the number of subarrays with a non-negative sum.

inputFormat

The first line contains two integers \(N\) and \(P\) separated by a space (\(1 \leq N \leq 10^5\), \(\lvert P \rvert \leq 10^9\)).

The second line contains \(N\) integers: \(a_1, a_2, \dots, a_N\), where \(\lvert a_i \rvert \leq 10^9\).

outputFormat

Output one integer, representing the number of continuous subarrays whose average price is at least \(P\).

sample

5 3
3 1 4 1 5

5