Contiguous Subarrays with Sufficient Median

Farmer John has lined up his N cows in a row. Each cow i has a height \(H_i\) (in nanometers). He wants to take a picture of a contiguous subsequence of cows for a contest where the photo is valid only if its median height is at least \(X\). The median of a sequence \(A[1\ldots K]\) (when sorted in non-decreasing order) is defined as \(A[\lceil K/2 \rceil]\). For example, the median of \(\{7, 3, 2, 6\}\) (which sorts to \(\{2, 3, 6, 7\}\)) is \(3\) if \(K=4\) (since \(\lceil4/2\rceil=2\)) and the median of \(\{5, 4, 8\}\) is \(5\) (since \(\lceil3/2\rceil=2\)).

Help Farmer John count the number of contiguous subsequences (subarrays) whose median is at least \(X\).

Hint: A useful approach is to transform each cow's height \(H_i\) into a value \(b_i\) defined as:

[ b_i = \begin{cases} 1 & \text{if } H_i \ge X, \ -1 & \text{if } H_i < X. \end{cases} ]

Then, if you define a prefix sum \(P[0]=0\) and \(P[i]=P[i-1]+b_i\) for \(i\ge1\), one can show that a subarray corresponding to indices \([i+1, j]\) has a median of at least \(X\) if and only if:

[ P[j] - P[i] \ge 1. ]

This problem can then be solved using a Fenwick tree (Binary Indexed Tree) after applying coordinate compression to the prefix sums.

inputFormat

The first line contains two integers \(N\) and \(X\) (\(1 \le N \le 100\,000\) and \(1 \le X \le 1\,000\,000\,000\)).

The second line contains \(N\) integers \(H_1, H_2, \dots, H_N\) (\(1 \le H_i \le 1\,000\,000\,000\)), representing the heights of the cows.

outputFormat

Output a single integer: the number of contiguous subsequences whose median is at least \(X\).

sample

4 4
4 3 5 6

7