Problem: K Average Ranges

Given the sequence a_1, a_2, .., a_N.

How many intervals in this sequence have an average value of K or more and a length of 1 or more?

input


N K
a_1 a_2 ... a_N


output

Output the answer.

Constraint

* 1 \ leq N \ leq 10 ^ 5
* 1 \ leq K \ leq 10 ^ 9
* 1 \ leq a_i \ leq 10 ^ 9



Input example


6 6
8 6 9 1 2 1


Output example


7






Example

Input

6 6
8 6 9 1 2 1


Output

7

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll inf = 3e18;
const char sp = ' ';

int N, K, a[100000], tree[1 << 18];
ll s[100001];

int calc(int x) {
	x += (1 << 17);
	int t = 0;
	while (x) {
		t += tree[x];
		x /= 2;
	}
	return t;
}

void update(int l, int r, int p, int q, int k) {
	if (r < p || q < l)return;
	if (p <= l && r <= q)tree[k]++;
	else {
		update(l, (l + r) / 2, p, q, k + k);
		update((l + r) / 2 + 1, r, p, q, k + k + 1);
	}
}

int main() {
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> a[i];
		a[i] -= K;
	}
	vector<ll>v{ 0 };
	for (int i = 0; i < N; i++) {
		s[i + 1] = s[i] + a[i];
		v.push_back(s[i + 1]);
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	ll res = 0;
	for (int i = 0; i <= N; i++) {
		res += calc(lower_bound(v.begin(), v.end(), s[i]) - v.begin());
		update(0, (1 << 17) - 1, lower_bound(v.begin(), v.end(), s[i]) - v.begin(), (1 << 17) - 1, 1);
	}
	cout << res << endl;
}