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;
using i64 = long long;

struct BIT
{
  i64 n;
  vector<i64> bit;

  BIT(i64 _n)
  {
    n = _n;
    bit.resize(n);
    fill(bit.begin(), bit.end(), 0);
  }

  void add(i64 idx, i64 x)
  {
    for (i64 i = idx; i <= n; i += i & -i)
      bit[i] += x;
  }

  i64 sum(i64 end)
  {
    i64 ret = 0;
    for (i64 i = end; i >= 1; i -= i & -i)
      ret += bit[i];
    return ret;
  }
};

int main()
{
  i64 n, k;
  cin >> n >> k;
  vector<i64> a(n + 1);
  for (i64 i = 1; i <= n; i++)
  {
    cin >> a[i];
    a[i] += (i ? a[i - 1] : 0LL) - k;
  }
  vector<i64> sorted_a = a;
  sort(sorted_a.begin(), sorted_a.end());
  i64 ans = 0;
  BIT bit(n + 2);
  for (i64 i = n; i >= 0; --i)
  {
    i64 idx = lower_bound(sorted_a.begin(), sorted_a.end(), a[i]) - sorted_a.begin() + 1;
    if (i != n)
      ans += n - i - bit.sum(idx - 1);
    bit.add(idx, 1);
  }
  cout << ans << endl;
  return 0;
}