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;

template<class T> struct FenwickTree {
  const int n;
  vector<T> t;
  FenwickTree(int _n) : n(_n), t(n + 1) {}
  void add(int i, T x) { for (++i; i <= n; i += i & -i) t[i] += x; }
  T sum(int i) const {
    T s = 0;
    for (; i; i -= i & -i) s += t[i];
    return s;
  }
  T sum(int l, int r) const { return sum(r) - sum(l); }
};

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (auto&& e : a) {
    cin >> e;
    e -= k;
  }
  vector<long long> c(n + 1);
  for (int i = 0; i < n; ++i) {
    c[i + 1] = c[i] + a[i];
  }
  auto v = c;
  sort(begin(v), end(v));
  v.erase(unique(begin(v), end(v)), end(v));
  for (auto&& e : c) {
    e = lower_bound(begin(v), end(v), e) - begin(v);
  }
  FenwickTree<int> ft(n + 1);
  long long res = 0;
  for (int i = 0; i <= n; ++i) {
    res += ft.sum(c[i] + 1);
    ft.add(c[i], 1);
  }
  cout << res << '\n';
}