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 <iostream>
#include <vector>
#include <array>
#include <list>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <tuple>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>
#include <cassert>
#include <random>
class Bit {
	std::vector<int> vec;
public:
	Bit(int size) : vec(size, 0) {}
	void add(int position, int value) {
		while (position < vec.size()) {
			vec[position] += value;
			position += ~position & (position + 1);
		}
	}
	int get(int position) const {
		int result = 0;
		while (position >= 0) {
			result += vec[position];
			position -= ~position & (position + 1);
		}
		return result;
	}
};
int main() {
	int n; long long int k; std::cin >> n >> k;
	std::vector<long long int> values(n); for (auto& v : values) std::cin >> v;
	std::vector<long long int> sum{ 0 }; for (auto v : values) sum.push_back(sum.back() + v);
	std::vector<int> indices(n + 1); std::iota(indices.begin(), indices.end(), 0);
	std::sort(indices.begin(), indices.end(), [&sum, k](int a, int b) {return (sum[a] - a * k == sum[b] - b * k) ? a < b : (sum[a] - a * k < sum[b] - b * k); });
	Bit bit(n + 1);
	long long int count = 0;
	for (const auto idx : indices) {
		count += bit.get(idx);
		bit.add(idx, 1);
	}
	std::cout << count << std::endl;
}