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;

#define REP(i, a) for(int64 i = 0; i < (a);i++)
#define FOR(i, a, b) for(int64 i = (a); i < (b); i++)
#define INF (int64)1e9
#define INF_LL (int64)1e18
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int32_t;
using int64 = int64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

template<typename A, typename B> inline void chmin(A &a, B b) { if (a > b) a = b;}
template<typename A, typename B> inline void chmax(A &a, B b) { if (a > b) a = b;}

template<typename CommutativeMonoid>
class FenwickTree{
public:
  using value_structure = CommutativeMonoid;
  using value_type = typename CommutativeMonoid::value_type;
  using size_type = ::std::size_t;

private:
  ::std::vector<value_type> tree;
  size_type N;

  static value_type calc(const value_type& a, const value_type& b){
    return value_structure::operation(a, b);
  }

public:
  FenwickTree(){}
  FenwickTree(const size_type& N):N(N+10), tree(N+11, value_structure::identity()){}
  FenwickTree(const FenwickTree& bit):tree(bit.tree), N(bit.N){}

  void update(size_type k, const value_type& diff){ // update k in [1, N]
    for(;k <= N;k += k & -k){
      tree[k] = calc(tree[k], diff);
    }
  }

  value_type query(size_type k) const { // sum of [1, k]
    value_type res = value_structure::identity();
    for(;k > 0;k -= k & -k){
      res = calc(res, tree[k]);
    }
    return res;
  }

  void updatez(size_type k, value_type v){ // 0-indexed
    update(k+1, v);
  }

  value_type queryz(size_type k) const { // [0, k)
    return query(k);
  }

  size_type search(const std::function<bool(value_type)>& f) const { // Find k :[0, k) -> True, [0, k-1) -> False
    if(f(value_structure::identity()))
      return 0;
    if(!f(query(N)))
      return N+1;
    value_type x = value_structure::identity();
    size_type k = 1, idx = 0;
    while(k <= N) k <<= 1;
    k >>= 1;
    for(;k > 0;k >>= 1){
      if((idx|k) <= N && !f(tree[idx|k]+x))
        x = calc(x, tree[idx |= x]);
    }
    return idx+1;
  }

  size_type size() const {return N;}
};

class v_monoid {
public:
  using value_type = int64;
  static const value_type identity() { return 0; }
  static const value_type operation(const value_type& a, const value_type& b) {
    return a + b;
  }
};

int main(void) {
  int64 N, K;
  cin >> N >> K;
  vector<int64> a(N), za(N);
  REP(i, N) {
    cin >> a[i]; a[i] -= K;
    if (i) a[i] += a[i-1];
    za[i] = a[i];
  }
  sort(all(za)); za.erase(unique(all(za)), za.end());
  REP(i, N) a[i] = lower_bound(all(za), a[i]) - za.begin();
  FenwickTree<v_monoid> bit(N);
  int64 res = 0;
  REP(i, N) {
    res += bit.queryz(a[i]+1);
    if (za[a[i]] >= 0) res++;
    bit.updatez(a[i], 1);
  }
  cout << res << endl;
}