P3031 [USACO11NOV] Above the Median G

Farmer John has lined up his N (1

\* Line 1: Two space-separated integers: N and X. \* Lines 2..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}.