Above the Median

Farmer John has lined up his $N$ ($1 \le N \le 100{,}000$) cows in a row to measure their heights; cow $i$ has height $H_i$ ($1 \le H_i \le 10^9$) nanometers—FJ believes in precise measurements! He wants to take a picture of some contiguous range of the cows to submit to a bovine photography contest at the county fair.

The contest has an unusual rule: a photograph may be submitted only if the cows it shows have a median height of at least a threshold $X$ ($1 \le X \le 10^9$).

For this problem, the median of an array $A[0..K]$ (which has $K+1$ elements) is defined as $A[\lceil K/2 \rceil]$ after $A$ is sorted in non-decreasing order, where $\lceil K/2 \rceil$ is $K/2$ rounded up (or $K/2$ itself when it is already an integer). For example, the median of $\{7, 3, 2, 6\}$ is $6$, and the median of $\{5, 4, 8\}$ is $5$.

Count the number of distinct contiguous ranges of cows that FJ could submit to the contest.

• Line 1: Two space-separated integers $N$ and $X$.
• Lines 2 to $N+1$: Line $i+1$ contains the single integer $H_i$.

• Line 1: The number of contiguous ranges whose median is at least $X$. This value may not fit in a 32-bit integer.