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 <algorithm>
#include <vector>
#include <map>
using namespace std;
#pragma warning (disable: 4996)

class BIT {
public:
	int size_;
	vector<int> bit;

	void init(int sz) {
		size_ = sz + 2;
		bit.resize(size_ + 2, 0);
	}
	void add(int pos, int x) {
		pos++;
		while (pos <= size_) {
			bit[pos] += x;
			pos += (pos & -pos);
		}
	}
	int sum(int pos) {
		pos++; int s = 0;
		while (pos >= 1) {
			s += bit[pos];
			pos -= (pos & -pos);
		}
		return s;
	}
};

long long N, K, A[1 << 18];

int main() {
	scanf("%lld%lld", &N, &K);
	for (int i = 1; i <= N; i++) { scanf("%lld", &A[i]); A[i] -= K; }
	for (int i = 1; i <= N; i++) A[i] += A[i - 1];

	vector<long long> val;
	for (int i = 0; i <= N; i++) val.push_back(A[i]);
	sort(val.begin(), val.end());
	for (int i = 0; i <= N; i++) A[i] = lower_bound(val.begin(), val.end(), A[i]) - val.begin();

	BIT C; C.init(val.size() + 2);
	C.add(A[0], 1);

	long long ans = 0;
	for (int i = 1; i <= N; i++) {
		ans += C.sum(A[i]);
		C.add(A[i], 1);
	}
	cout << ans << endl;
	return 0;
}