P3031 [USACO11NOV] Above the Median G

Farmer John has lined up his $N(1\le N\le 10^5)$ 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 subsequence of the cows to submit to a bovine photography contest at the county fair. The fair has a very strange rule about all submitted photos: a photograph is only valid to submit if it depicts a group of cows whose median height is at least a certain threshold $X (1\le X\le 10^9)$. For the purposes of this problem, we define the median of an array $A_{0\dots K}$ to be $A_{\lceil\frac{K}{2}\rceil}$ after $A$ is sorted, where $\lceil\frac{K}{2}\rceil$ gives $\frac{K}{2}$ rounded up to the nearest integer (or $\frac{K}{2}$ itself, if $\frac{K}{2}$ is an integer to begin with). For example, the median of $\{7, 3, 2, 6\}$ is $6$, and the median of $\{5, 4, 8\}$ is $5$. Please help FJ count the number of different contiguous subsequences of his cows that he could potentially submit to the photography contest. Given a sequence of numbers, count how many contiguous subsequences have a median greater than or equal to $X$. For an even count, the median is defined as the higher middle value rather than the average.

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

- Line $1$: The number of subsequences of FJ's cows that have median at least $X$. Note this may not fit into a 32-bit integer.

FJ's four cows have heights $10, 5, 6, 2$. We want to know how many contiguous subsequences have median at least $6$. There are $10$ possible contiguous subsequences to consider. Of these, only $7$ have median at least $6$. They are $\{10\}, \{6\}, \{10, 5\}, \{5, 6\}, \{6, 2\}, \{10, 5, 6\}, \{10, 5, 6, 2\}$.