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>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define SIZE 100005

int N;
ll BIT[SIZE];
ll table[SIZE];
map<ll,int> MAP;

void add(int loc,ll value){

	BIT[loc] += value;

	loc += loc & -loc;

	while(loc <= N){
		BIT[loc] += value;
		loc += loc & -loc;
	}
}

ll getSum(int loc){

	ll sum = BIT[loc];

	loc -= loc & -loc;

	while(loc > 0){
		sum += BIT[loc];
		loc -= loc & -loc;
	}
	return sum;
}

ll calc(int left,int right){
	return getSum(right)-getSum(left-1);
}

int main(){

	int first_N;
	ll K;
	scanf("%d %lld",&first_N,&K);

	ll sum = 0,tmp;
	vector<ll> V;
	V.push_back(0);

	for(ll i = 0; i < first_N; i++){

		scanf("%lld",&tmp);
		sum += tmp;
		table[i] = sum-(i+1)*K;
		V.push_back(table[i]);
	}

	sort(V.begin(),V.end());
	V.erase(unique(V.begin(),V.end()),V.end());

	for(int i = 0; i < V.size(); i++){

		MAP[V[i]] = i+1;
	}

	N = V.size();

	for(int i = 0; i <= N; i++){

		BIT[i] = 0;
	}

	ll ans = 0;
	add(MAP[0],1);

	for(int i = 0; i < first_N; i++){

		ans += getSum(MAP[table[i]]);
		add(MAP[table[i]],1);
	}

	printf("%lld\n",ans);

	return 0;
}