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
// Exactly same as https://atcoder.jp/contests/arc075/submissions/1324786

#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
#pragma warning(disable : 4996)
using namespace std;
int N, K, p[200009], bit[200009]; long long a[200009];
int main() {
	scanf("%d %d", &N, &K);
	for (int i = 0; i < N; i++) scanf("%lld", &a[i + 1]), a[i + 1] += a[i] - K, p[i + 1] = i + 1;
	sort(p, p + N + 1, [](int i, int j) { return a[i] != a[j] ? a[i] < a[j] : i < j; });
	long long ret = 0;
	for (int i = 0; i <= N; i++) {
		for (int j = p[i]; j >= 1; j -= j & (-j)) ret += bit[j];
		for (int j = p[i] + 1; j <= N; j += j & (-j)) bit[j]++;
	}
	printf("%lld\n", ret);
	return 0;
}
