**Solution Notes:** If we replace each number less than X with
-1 and each number greater than or equal to X with +1, then this
problem reduces to counting the number of subarrays with nonnegative
sums. There are a few ways to approach this. First, suppose we
instead consider the complementary problem of counting the number of
subarrays with negative sums. If we precompute an array P of prefix
sums (so P[j] gives the sum of A[1...j]), subrrays A[i+1..j] with
negative sums correspond to pairs (i,j) with i < j but P[i] > P[j].
Such pairs are called "inversions" in P, and counting inversions is a
relatively standard algorithmic problem; this can be done in O(n log
n) time, for example, via divide and conquer using a modified merge
sort. In fact, with this particular problem, we can count the
inversions in just O(n) time, as we will see shortly, owing to the
fact that P[i+1] differs from P[i] by either -1 or +1.

A relatively simple O(n log n) solution due to Nathan Pinsker is shown below. It counts inversions using a binary index tree -- a useful data structure for many contest problems since it can be coded very quickly. The binary index tree implicitly encodes an array A[1..n] and supports two operations: query(p), which returns the sum of the prefix A[1..p], and update(p), which changes the value of A[p] (in our case here, we only need to increment A[p]).

```
#include <cstdio>
using namespace std;
#define MAXN 100005
int n, x, a[MAXN], b[2 * MAXN], s;
long long total;
FILE *in = fopen("median.in", "r"), *out = fopen("median.out", "w");
int query(int p) {
int t = 0;
for (int i=(p + MAXN); i; i -= (i & -i)) {
t += b[i];
}
return t;
}
void update(int p) {
for (int i=(p + MAXN); i < 2*MAXN; i += (i & -i)) {
b[i]++;
}
}
int main() {
fscanf(in, "%d%d", &n, &x);
for (int i=0; i<n; ++i) {
fscanf(in, "%d", &a[i]);
a[i] = (a[i] >= x ? 1 : -1);
}
update(0);
for (int i=0; i<n; ++i) {
s += a[i];
total += query(s);
update(s);
}
fprintf(out, "%lld\n", total);
return 0;
}
```

An even more concise O(n) solution is below, based on an approach suggested by Stan Zhang.
Here, the idea is to count inversions as we go, as before, but to update our count somewhat
carefully at each step. For each j, we want to count the number of indices i < j for
which P[i] > P[j]. To do so, we keep a running count in b[x+MAXN] of the number of indices
i < j with P[i] = x (that is, we keep a running count of how many times each prefix sum has
occurred so far). Letting t be the number of indices i < j for which P[i] > P[j], we can update
t as j moves to j+1 by either adding or subtracting an element of this b array, owing to the
fact that P[j+1] is either one higher or one lower than P[j]. In the code below, s keeps
track of our running prefix sum.
```
#include <cstdio>
using namespace std;
#define MAXN 100005
int n, x, a, b[2 * MAXN], s = MAXN;
long long total, t;
FILE *in = fopen("median.in", "r"), *out = fopen("median.out", "w");
int main() {
fscanf(in, "%d %d", &n, &x);
total = (long long)n*(n+1)/2;
b[MAXN] = 1;
for (int j=0; j<n; ++j) {
fscanf(in, "%d", &a);
if (a >= x) { s++; t-=b[s]; }
else { t+=b[s]; s--; }
b[s]++;
total -= t;
}
fprintf(out, "%lld\n", total);
return 0;
}
```