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 <cassert>
#include <cstddef>
#include <vector>

template <class Monoid> class segment_tree {
public:
  using T = typename Monoid::value_type;
  using size_t = std::size_t;

private:
  std::vector<T> tree;

  template <class F>
  size_t search_subtree(size_t index, const F f, T fold_l) const {
    while (index < size()) {
      const T temp = Monoid::operation(fold_l, tree[index * 2]);
      if (!f(temp)) {
        index = index * 2;
      } else {
        fold_l = temp;
        index = index * 2 + 1;
      }
    }
    return index - size();
  }

public:
  segment_tree() = default;
  explicit segment_tree(const size_t n) : tree(n * 2, Monoid::identity) {}

  size_t size() const noexcept { return tree.size() / 2; }

  T fold(size_t first, size_t last) const {
    assert(first <= last);
    assert(last <= size());
    first += size();
    last += size();
    T fold_l = Monoid::identity;
    T fold_r = Monoid::identity;
    while (first != last) {
      if (first % 2 != 0) {
        fold_l = Monoid::operation(fold_l, tree[first]);
        first += 1;
      }
      first /= 2;
      if (last % 2 != 0) {
        last -= 1;
        fold_r = Monoid::operation(tree[last], fold_r);
      }
      last /= 2;
    }
    return Monoid::operation(fold_l, fold_r);
  }
  template <class F> size_t search(size_t first, size_t last, const F f) const {
    assert(first <= last);
    assert(last <= size());
    first += size();
    last += size();
    const size_t last_cp = last;
    size_t shift = 0;
    T fold_l = Monoid::identity;
    while (first != last) {
      if (first % 2 != 0) {
        const T temp = Monoid::operation(fold_l, tree[first]);
        if (!f(temp))
          return search_subtree(first, f, fold_l);
        fold_l = temp;
        first += 1;
      }
      first /= 2;
      last /= 2;
      shift += 1;
    }
    while (shift != 0) {
      shift -= 1;
      last = last_cp >> shift;
      if (last % 2 != 0) {
        last -= 1;
        const T temp = Monoid::operation(fold_l, tree[last]);
        if (!f(temp))
          return search_subtree(last, f, fold_l);
        fold_l = temp;
      }
    }
    return last_cp - size();
  }

  void update(size_t index, const T x) {
    assert(index < size());
    index += size();
    tree[index] = x;
    while (index != 1) {
      index /= 2;
      tree[index] = Monoid::operation(tree[index * 2], tree[index * 2 + 1]);
    }
  }
};

#include<iostream>
#include<cstddef>
#include<cstdint>
#include<vector>
#include<algorithm>
#include<map>
using usize=std::size_t;
using i64 = std::int_fast64_t;

struct sum{
  using value_type=i64;
  static i64 operation(i64 l,i64 r){return l+r;}
  static constexpr i64 identity=0;
};
constexpr i64 sum::identity;

int main(){
  usize n;
  i64 k;
  std::cin>>n>>k;
  std::vector<i64> a(n);
  for(auto&e:a){
    std::cin>>e;
    e-=k;
  }
  std::vector<i64> rui(n+1);
  rui[0]=0;
  for(usize i=0;i<n;++i)rui[i+1]=rui[i]+a[i];

  std::map<i64,usize> mp;
  for(auto &e:rui)mp[e];
  {
    usize cnt=0;
    for(auto &e:mp)e.second=cnt++;
  }

  i64 ans=0;

  segment_tree<sum> seg(mp.size());
  for(const auto e:rui){
    ans+=seg.fold(0,mp[e]+1);
    seg.update(mp[e],seg.fold(mp[e],mp[e]+1)+1);
  }

  std::cout<<ans<<std::endl;
}