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>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

struct SegTree {
	std::unordered_map<int64_t, int> data;
	int64_t n;
	SegTree (int64_t n_) {
		for (n = 1; n < n_; n <<= 1);
	}
	void add(int64_t i, int val) {
		for (i += n; i; i >>= 1) data[i] += val;
	}
	int get(int64_t l, int64_t r) {
		int sum = 0;
		for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if (r & 1) sum += data[--r];
			if (l & 1) sum += data[l++];
		}
		return sum;
	}
};

int main() {
	int n = ri(), k = ri();
	int a[n];
	for (auto &i : a) i = ri() - k;
	int64_t sum[n + 1];
	sum[0] = 0;
	for (int i = 0; i < n; i++) sum[i + 1] = sum[i] + a[i];
	for (auto &i : sum) i += 100000000000000000;
	SegTree tree(1000000000000000000);
	int64_t res = 0;
	for (int i = 1; i <= n; i++) {
		tree.add(sum[i - 1], 1);
		res += tree.get(0, sum[i] + 1);
	}
	std::cout << res << std::endl;
	return 0;
}