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 <vector>
#include <algorithm>
using namespace std;
int k;
int bit[1000010];
void add(int a,int w){
  for(int i = a; i <= k; i += i & -i)bit[i] += w;
}
int sum(int a){
  int ret = 0;
  for(int i = a; i > 0; i -= i & -i) ret += bit[i];
  return ret;
}
int main(){
  long long n,m;cin>>n>>m;
  vector<long long> a(n);
  for(int i = 0; n > i; i++){
    cin>>a[i];
    a[i] -= m;
  }
  vector<long long> b(n+1);
  vector<long long> c(n+1);
  b[0] = 0;
  c[0] = 0;
  for(int i = 1; n >= i; i++){
    b[i] = b[i-1]+a[i-1];
    c[i] = b[i];
  }
  sort(c.begin(),c.end());
  c.erase(unique(c.begin(),c.end()),c.end());
  vector<long long> d(c.size());
  for(int i = 0; n >= i; i++){
    auto z = lower_bound(c.begin(),c.end(),b[i]) - c.begin();
    d[z]++;
  }
  k = c.size();
  for(int i = 1; k >= i; i++){
    //cout << d[i-1] << endl;
    add(i,d[i-1]);
  }
  long long ans = 0;
  for(int i = 0; n >= i; i++){
    
    auto z = lower_bound(c.begin(),c.end(),b[i]) - c.begin();
    ans += max(0,sum(k)-sum(z)-1);
    //cout <<sum(z) << endl;
    //cout <<":" << b[i] << " " << z << endl;
    add(z+1,-1);
  }
  cout << ans << endl;

}