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>
using namespace std;
typedef long long ll;


long long n;
long long bit[2010000];

//aの位置にwを追加
void add(long long a,long long w){
    a++;
    for(int x=a;x<=n+1;x+=(x&(-x)) ){
        bit[x] += w;
    }
}

//v[0] + ... + v[a-1]
long long sum(long long a){
    long long ret=0;
    for(int x=a;x>0;x-=(x&(-x)) ){
        ret+=bit[x];
    }
    return ret;
}


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
    
    ll k;
    cin>>n>>k;
    map<ll,ll> mp;
    ll a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
        a[i] -= k;
        if(i) a[i] += a[i-1];
        mp[a[i]]=0;
    }
    ll cnt = 0;
    mp[-1e18]=0;
    for(auto &i:mp){
        i.second = cnt;
        cnt++;
    }
    ll ans = 0;
    for(int i=0;i<n;i++){
        if(a[i]>=0) ans++;
        ans += sum(mp[a[i]]+1);
        add(mp[a[i]],1);
    }
    cout << ans << endl;
}