Ta gọi ~k~ thanh gỗ độ dài ~l_1, l_2, ... , l_k~ là đẹp nếu có cách phân chia chúng thành ba tập khác rỗng, sau đó ghép nối các thanh gỗ trong cùng một tập thành một đoạn có độ dài là tổng độ dài các thanh gỗ trong tập, khi đó độ dài của ba đoạn đó là độ dài ba cạnh của một tam giác.

Hiện có ~n~ thanh gỗ xếp thành một hàng từ trái sang phải với độ dài tương ứng là ~d_1, d_2, ... , d_n~, các thanh gỗ có độ dài đôi một khác nhau. Với số nguyên ~k \ge 3~, ta cần đếm xem có bao nhiêu cách chọn ~k~ thanh gỗ liên tiếp nhau mà ~k~ thanh gỗ này là đẹp.

Input

Dòng đầu tiên gồm các số ~n,k~ với ~3 \le k \le n \le 10^5.~

Dòng tiếp theo gồm ~n~ số nguyên dương đôi một khác nhau và không vượt quá ~10^9.~

Output

Số cách chọn thỏa mãn đề bài.

Sample input

6 3
1 3 4 2 5 9

Sample output

2

Subtasks

• Có ~20\%~ số test có ~k = n = 3;~

• Có ~20\%~ số test khác có ~k = n = 4;~

• Có ~20\%~ số test khác có ~k = n \le 10;~

• Có ~20\%~ số test khác có ~k \le n \le 1000;~

• Có ~20\%~ số test còn lại là theo giới hạn ban đầu.