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 <cstring>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <fstream>

using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007
#define P pair<ll, ll>

ll now, ans, n, k, r[110000];
ll q;
map<ll, ll> m;
//セグ木
ll dat[2560000], sz;

void init(ll n) {
	sz = 1;
	while (sz < n)sz *= 2;
}

void update(ll k, ll a) { //場所(0-indexed), 値
	k += sz - 1;
	dat[k] = a;
	while (k > 0) {
		k = (k - 1) / 2;
		dat[k] = dat[k * 2 + 1] + dat[k * 2 + 2]; //更新
	}
}

ll query(ll a, ll b, ll k, ll l, ll r) { //[a, b) 呼ぶとき (a, b, 0, 0, sz)
	if (r <= a or b <= l)return 0;
	if (a <= l and r <= b)return dat[k];
	ll v1 = query(a, b, k * 2 + 1, l, (l + r) / 2);
	ll v2 = query(a, b, k * 2 + 2, (l + r) / 2, r);
	return v1 + v2; //戻り値
}

int main() {
	init(110000);
	cin >> n;
	cin >> k;
	vector<ll> s(n);
	REP(i, n) {
		cin >> s[i];
		s[i] -= k;
	}
	m[0] = 0;
	REP(i, n) {
		r[i + 1] = r[i] + s[i];
		m[r[i + 1]] = 0;
	}
	for (auto& i : m) {
		i.second = now;
		now++;
	}
	REP(i, n + 1) {
		ans += query(0, m[r[i]] + 1, 0, 0, sz);
		update(m[r[i]], query(m[r[i]], m[r[i]] + 1, 0, 0, sz) + 1);
	}
	cout << ans << endl;
}