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"
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

typedef long long ll;

const int MAX_N = 1e5;

int bit[MAX_N + 1], n;

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

void add(int i, int x) {
    while (i <= n) {
        bit[i] += x;
        i += i & -i;
        //cout << i << " ";
    }
    //cout << endl;
}

int main() {
    int N, K;
    cin >> N >> K;
    vector<ll> a(N), s(N + 1, 0);
    map<ll, int> m;
    m[0] = 1;
    rep(i, N) {
        cin >> a[i];
        a[i] -= K;
        s[i + 1] = s[i] + a[i];
        m[s[i + 1]]++;
    }
    /*
    for (auto i : m) {
        cout << i.first << " " << i.second << endl;
    }
    */
    int j = 1;
    n = m.size();
    for (auto i : m) {
        int l = i.second;
        //cout << i.first << " " << i.second << endl;
        add(j, l);
        m[i.first] = j;
        j++;
    }
    /*
    for (auto i : m) {
        cout << i.first << " " << i.second << endl;
    }
    */
    rep(i, N + 1) {
        s[i] = m[s[i]];
        //cout << s[i];
    }
    //cout << endl;
    //cout << n << endl;
    //rep(i, n) cout << sum(i) << " ";
    //cout << endl;
    ll ans = 0;
    rep(i, N + 1) {
        add(s[i], -1);
        //rep(j, n) cout << bit[j] << " ";
        //cout << endl;
        ans += sum(n);
        if (s[i] > 0) ans -= sum(s[i] - 1);
        //cout << ans << endl;
    }
    cout << ans << endl;
}