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 SZ(x) (int)(x.size())

using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, k; scanf("%d %d", &n, &k);
  vll a(n);
  vector<ll> st;
  ll su = 0;
  for(int i=0;i<n;++i) {
    scanf("%ld", &a[i]);
    a[i] -= k;
    su += a[i];
    //cout << su << endl;
    st.push_back(su);
  }
  sort(st.begin(), st.end());

  ll minus = 0;
  ll cnt = 0;
  for(int i=0;i<n;++i) {
    //cout << i << endl;
    auto it = lower_bound(st.begin(), st.end(), minus);
    cnt += distance(it, st.end());
    //cout << distance(it, st.end()) << endl;
    auto del = find(st.begin(), st.end(), a[i] + minus);
    st.erase(del);
    minus += a[i];
  }

  cout << cnt << endl;  
}