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 JAVA):

Solution:
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextInt();
        long[] arr = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = arr[i - 1] + sc.nextInt() - k;
        }
        ArrayList<Long> list = new ArrayList<>();
        list.add(Long.MIN_VALUE);
        list.add(0L);
        list.add(Long.MAX_VALUE);
        long count = 0;
        for (int i = 1; i <= n; i++) {
            int left = 0;
            int right = list.size() - 1;
            while (right - left > 1) {
                int m = (left + right) / 2;
                if (arr[i] < list.get(m)) {
                    right = m;
                } else {
                    left = m;
                }
            }
            count += left;
            list.add(right, arr[i]);

        }
        System.out.println(count);
    }
}