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 all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
constexpr ll INF = (1LL << 30) - 1LL;
constexpr ll LINF = (1LL << 60) - 1LL;
constexpr ll MOD = 1e9 + 7;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }
template <typename T> struct BinaryIndexedTree {
    vector<T> node;
    int n;
    BinaryIndexedTree(int n) : n(n) { node.assign(++n, 0); }
    void add(int k, T x) {
        for (++k; k < n; k += k & -k) {
            node[k] += x;
        }
    }
    T sum(int k) {
        T res = 0;
        for (++k; k > 0; k -= k & -k) {
            res += node[k];
        }
        return res;
    }
};
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n), sum(n + 1);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum[i + 1] = sum[i] + a[i];
    }
    vector<ll> v;
    v.push_back(0);
    for (int i = 1; i <= n; i++) {
        v.push_back(sum[i] - k * i);
    }
    sort(all(v));
    v.erase(unique(all(v)), v.end());
    BinaryIndexedTree<ll> bit(v.size() + 1);
    bit.add(lower_bound(all(v), 0) - v.begin(), 1);
    ll res = 0;
    for (int i = 1; i <= n; i++) {
        int t = lower_bound(all(v), sum[i] - k * i) - v.begin();
        res += bit.sum(t);
        bit.add(t, 1);
    }
    cout << res << endl;
}