In this task, we need to find the number of consecutive subsequences such that the average value is ~\ge P~.

To begin with, it is important to notice that, if we subtract the value ~P~ from each number, we have reduced the task to finding the number of consecutive subsequences such that their sum is non-negative.

Therefore, now the task is to find the number of consecutive subsequences that have the sum of values non-negative in the sequence of numbers. We can do this in two ways, one of which will be described here, while the official solution implements the other.

Let ~pref(x)~ be the sum of the first ~x~ elements in the transformed sequence. It is easy to see that the sum of elements in the interval ~[L, R] = pref(R)-pref(L-1)~. Because we are searching for a number in the interval ~[L, R]~, we can calculate how many positions ~L~ there are so that the sum in the interval ~[L, R]~ is non-negative for each ~R~. Therefore, for each ~pref(R)~ we ask how many ~pref(L-1)~ there are such that ~L \le R~ and ~pref(R) \ge pref(L-1)~. If we imagine that we are moving from left to right in the array, for each ~R~ we need to be able to answer how many ~pref(L-1) \le pref(R)~, ~L \le R~ there are.

Because we only want to know about the relative order between the prefix sums, we can hash the value of each prefix sum and convert it to a single number from the interval ~[0, N)~, depending on their relative order. The hashing needs to be implemented in order to efficiently answer queries using a data structure. The simplest data structure to implement that enables inserting number ~X~ and querying how many numbers smaller than ~Y~ there are is the Fenwick tree data structure. For details about this data structure, consult https://wiki.xfer.hr/logaritamska_tutorial/. (DMOJ curator note: Good luck reading this.)