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;

#define For(i,a,b) for(long long (i) = (a);(i) < (b);i++)
#define Rep(i,n) For((i),0,(n))
#define All(a) (a).begin(),(a).end()
#define sp " "
#define INF 1e18
#define INT_INF 1e9
#define MAX_N 100000

typedef long long ll;
const ll MOD = 1000000007;
const ll MOD_9 = 998244353;

ll bit[MAX_N+1];
ll n;
ll k;

ll Sum(ll i){
    ll s = 0;
    while(i > 0){
        s += bit[i];
        i -= i & -i;
    }
    return s;
}

void add(ll i, ll x){
    while(i <= n){
        bit[i] += x;
        i += i & -i;
    }
}

int main(){
    cin >> n >> k;
    vector<ll> A(n+1);
    vector<ll> sum;
    vector<ll> B(n+1,0);
    vector<ll> t(n+1,0);
    ll ans = 0;
    A[0] = 0;
    B[0] = 0;
    sum.push_back(0);
    Rep(i,n){
        cin >> A[i+1];
        sum.push_back(sum[i] + A[i+1]);
        sum[i+1] -= k;
        B[i+1] = sum[i+1];
        //cout << sum[i+1] << endl;
    }
    //cout << endl;
    sort(All(B));
    B.erase(unique(B.begin(),B.end()),B.end());
    vector<ll> f(n+1);
    Rep(i,n+1){
        ll p = lower_bound(All(B),sum[i])-B.begin();
        f[i] = p+1;
        //cout << f[i] << endl;
    }
    Rep(i,n+1){ 
        t[i] = Sum(f[i]);
        //cout << t[i] << endl;
        ans += t[i];
        add(f[i],1);
    }
    cout << ans << endl;
    //cin >> n;
}