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:
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000000000000
#define MOD 1000000007
typedef pair<int, int> P;

bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n % i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int mod_pow(int n, int p, int m) {
	if (p == 0) return 1;
	if (p % 2 == 0) {
		int t = mod_pow(n, p / 2, m);
		return (t * t) % m;
	}
	return n * mod_pow(n, p - 1, m) % m;
}
int extGCD(int a, int b, int& x, int& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long d = extGCD(b, a % b, y, x);
	y -= a / b * x;
	return d;
}
int modinv(int a, int m) {
	int b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
int digit(int x) {
	int cnt = 0;
	while (x > 0) {
		cnt += x % 10;
		x /= 10;
	}
	return cnt;
}

class BIT {
private:
	vector<int>bit;
	int n;
public:
	BIT(int _n) {
		rep(i, _n + 1) bit.push_back(0);
		n = _n;
	}

	int get() {
		return bit.size();
	}

	int sum(int i) {
		int s = 0;
		while (i > 0) {
			s += bit[i];
			i -= (i & -i);
		}
		return s;
	}

	int sum(int i, int j) {
		int be = sum(i - 1);
		int af = sum(j);
		return af - be;
	}

	void add(int i, int x) {
		while (i <= n) {
			bit[i] += x;
			i += (i & -i);
		}
	}
};

signed main() {
	int n;
	int k;
	cin >> n >> k;
	int a[100005], sum[100005], x[100005];
	sum[0] = 0;
	rep(i, n) {
		cin >> a[i];
		a[i] -= k;
		sum[i + 1] = sum[i] + a[i];
	}
	rep(i, n + 1) {
		x[i] = sum[i];
	}
	sort(x, x + n + 1);
	map<int, int>mp;
	int now = 1;
	mp[x[0]] = 1;
	for (int i = 1; i < n + 1; i++) {
		if (x[i] > x[i - 1]) {
			now++;
		}
		mp[x[i]] = now;
	}
	rep(i, n + 1) {
		sum[i] = mp[sum[i]];
	}
	int ans = 0;
	BIT bit(n);
	for (int i = n - 1; i >= 0; i--) {
		bit.add(sum[i + 1], 1);
		ans += (n - i) - bit.sum(sum[i] - 1);
	}
	cout << ans << endl;

	return 0;
}