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 <set>
#include <algorithm>

using namespace std;
typedef long long ll;

int index(vector<ll> &v, ll x) {
    return lower_bound(v.begin(), v.end(), x) - v.begin();
}

template<typename T>
struct BinaryIndexedTree {
    vector<T> data;

    BinaryIndexedTree(int sz) {
        data.assign(++sz, 0);
    }

    T sum(int k) {
        T ret = 0;
        for (++k; k > 0; k -= k & -k) ret += data[k];
        return (ret);
    }

    void add(int k, T x) {
        for (++k; k < data.size(); k += k & -k) data[k] += x;
    }
};

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i] -= k;
    }

    vector<ll> c_sum(n + 1);
    for (int i = 0; i < n; i++)c_sum[i + 1] = c_sum[i] + a[i];

    vector<ll> sorted = c_sum;
    sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());

    BinaryIndexedTree<ll> bit(n + 1);
    ll ret = 0;
    for (int i = n; i >= 0; i--) {
        ret += (n - i) - bit.sum(index(sorted, c_sum[i]) - 1);
        bit.add(index(sorted, c_sum[i]), 1);
    }
    cout << ret << endl;
    return 0;
}