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 <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
#include <stdio.h>
#include <ctype.h>
using namespace std;
#define pie 3.141592653589793238462643383279
#define mod 1000000007
#define INF 1145141919364364
#define int long long
#define all(vec) vec.begin(),vec.end()
#define P pair<int,int>
#define S second
#define F first
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;
}
bool prime(int x) {
	for (int i = 2; i <= sqrt(x); i++) {
		if (x%i == 0)return false;
	}
	return true;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod;
}

int n, k, a[100000];
vector<int> vec;
map<int, int> mp;
int ans;

int bit[100010];
void add(int a, int w) {
	for (int x = a; x <= n; x += x & -x) bit[x] += w;
}
int sum(int a) {
	int ret = 0;
	for (int x = a; x > 0; x -= x & -x) ret += bit[x];
	return ret;
}

signed main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		if (!i)a[i] -= k;
		else a[i] = a[i - 1] + a[i] - k;
		vec.push_back(a[i]);
	}
	sort(all(vec));
	int cnt = 0;
	int zero = 0;
	if (vec[0] <= 0)cnt = 1;
	else {
		zero = 1;
		cnt = 2;
	}
	for (int i = 0; i < n; i++) {
		mp[vec[i]] = cnt;
		if (i < n - 1) {
			if (vec[i] != vec[i + 1]) {
				if (vec[i + 1] == 0)zero = cnt + 1;
				if (vec[i] < 0 && 0 < vec[i + 1]) {
					zero = cnt + 1;
					cnt += 2;
				}
				else cnt++;
			}
		}
	}
	if (!zero)zero = cnt + 1;
	for (int i = 0; i < n; i++) {
		a[i] = mp[a[i]];
	}
	add(zero, 1);
	for (int i = 0; i < n; i++) {
		ans += sum(a[i]);
		add(a[i], 1);
	}
	cout << ans << endl;
}