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;

mt19937 rnd;

template<typename T>
struct Treap{
    struct Node{
        T val, sum;
        int pri, cnt;
        Node *lch, *rch;
        Node(T v):val(v), sum(v), pri(rnd()), cnt(1){
            lch = rch = nullptr;
        }
    };

    Node* node;

    Treap(Node* n=nullptr){ node = n; }
    Treap(T v){ node = new Node(v); }
    void initialize(T v){ node = new Node(v); }

    int count(Node* t){ return !t ? 0 : t->cnt; }
    T   sum  (Node* t){ return !t ? 0 : t->sum; }
    int count(){ return count(node); }
    T   sum  (){ return sum  (node); }

    Node* update(Node* t){
        t->cnt = count(t->lch) + count(t->rch) + 1;
        t->sum =   sum(t->lch) +   sum(t->rch) + t->val;
        return t;
    }

    Node* merge(Node* l, Node* r){
        if(!l || !r) return !l ? r : l;
        if(l->pri > r->pri){
            l->rch = merge(l->rch, r);
            return update(l);
        }else{
            r->lch = merge(l, r->lch);
            return update(r);
        }
    }

    pair<Node*, Node*> split(Node* t, T v){
        if(!t) return make_pair(nullptr, nullptr);
        if(v < t->val){
            auto s = split(t->lch, v);
            t->lch = s.second;
            return {s.first, update(t)};
        }else{
            auto s = split(t->rch, v);
            t->rch = s.first;
            return {update(t), s.second};
        }
    }
    pair<Treap*, Treap*> split(T v){
        auto p = split(node, v);
        node = p.first;
        auto t2 = new Treap(p.second);
        return make_pair(this, t2);
    }

    void insert(T v){
        auto s = split(node, v);
        auto n = new Node(v);
        node = merge(s.first, n);
        node = merge(node, s.second);
    }

    void erase(T v){
        auto s1 = split(node, v-1);
        auto s2 = split(s1.second, v);
        node = merge(s1.first, s2.second);
    }

    int count_larger_than(Node* t, T v, bool larger){
        if(!t) return 0;
        int ret = 0;
        if(larger){
            if(v < t->val) ret++;
            ret += v < t->val ? count(t->rch) : count_larger_than(t->rch, v, larger);
            ret += v < t->val ? count_larger_than(t->lch, v, larger) : 0;
        }else{
            if(v > t->val) ret++;
            ret += v > t->val ? count(t->lch) : count_larger_than(t->lch, v, larger);
            ret += v > t->val ? count_larger_than(t->rch, v, larger) : 0;
        }
        return ret;
    }
    // vより大きい値の個数。larger=falseならvより小さい
    int count_larger_than(T v, bool larger=true){ return count_larger_than(node, v, larger); }

    T sum_larger_than(Node* t, T v, bool larger){
        if(!t) return 0;
        T ret = 0;
        if(larger){
            if(v < t->val) ret += t->val;
            ret += v < t->val ? sum(t->rch) : sum_larger_than(t->rch, v, larger);
            ret += v < t->val ? getsum(t->lch, v, larger) : 0;
        }else{
            if(v > t->val) ret += t->val;
            ret += v > t->val ? sum(t->lch) : sum_larger_than(t->lch, v, larger);
            ret += v > t->val ? sum_larger_than(t->rch, v, larger) : 0;
        }
        return ret;
    }
    // vより大きい値の総和。larger=falseならvより小さい
    T sum_larger_than(T v, bool larger=true){ return sum_larger_than(node, v, larger); }

    void dump(Node* t, vector<T>& ret){
        if(!t) return;
        dump(t->lch, ret);
        ret.push_back(t->val);
        dump(t->rch, ret);
    }
    vector<T> dump(){
        vector<T> ret;
        dump(node, ret);
        return ret;
    }

    void merge(Treap* tr){
        for(auto &&v : tr->dump) this->insert(v);
    }
};

int main(){
    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    for(int i=0; i<N; i++) cin >> A[i], A[i]-=K;

    int64_t s = 0;
    Treap<int64_t> tr(s);
    int64_t ans = 0;
    for(int a : A){
        s += a;
        ans += tr.count_larger_than(s+1, false);
        tr.insert(s);
    }
    cout << ans << endl;
    return 0;
}