Đoạn con của dãy số là một dãy các số được tạo thành từ các phần tử liên tiếp của dãy số ban đầu.

Độ đẹp của một dãy số là một số nguyên dương ~X~ nhỏ nhất, sao cho ta có thể chia dãy số ban đầu thành ~X~ đoạn con không giao nhau và tổng của tất cả các số trong mỗi đoạn con không lớn hơn ~S~. Ví dụ: Với ~S = 8~, đoạn ~[2,3,5]~ có thể chia thành hai hoặc ba đoạn có tổng mỗi đoạn con không lớn hơn ~S~: ~([2,3], [5])~ hoặc ~([2], [3,5])~ hoặc ~([2], [3], [5])~. Vì cần tìm ~X~ nhỏ nhất nên đoạn ~[2,5,3]~ có độ đẹp là 2.

Độ đẹp hoàn hảo của dãy số là tổng độ đẹp tất cả đoạn con của nó.

Yêu cầu: Cho dãy số nguyên dương ~A_1, A_2, \dots, A_N~. Tính độ đẹp hoàn hảo của dãy số đã cho.

Input

• Dòng thứ nhất chứa hai số nguyên dương ~N~ và ~S~ cách nhau một ký tự trống. (~N \le 10^5~, ~S \le 10^9~).
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, \dots, A_N~ (~A_i \le 10^6~) mỗi số cách nhau một ký tự trống.

Output

Một số nguyên duy nhất là kết quả của bài toán.

Sample Input 1

4 8
1 2 5 3

Sample Output 1

12

Dãy ~1, 2, 5, 3~ có các đoạn con là: ~[1], [2], [5], [3], [1,2], [2,5], [5,3], [1,2,5], [2,5,3], [1,2,5,3]~.

Trong đó: ~[1]~ có độ đẹp là 1, ~[2]~ có độ đẹp là 1, ~[5]~ có độ đẹp là 1, ~[3]~ có độ đẹp là 1, ~[1,2]~ có độ đẹp là 1, ~[2,5]~ có độ đẹp là 1, ~[5,3]~ có độ đẹp là 1, ~[1,2,5]~ có độ đẹp là 1, ~[2,5,3]~ có độ đẹp là 2, ~[1,2,5,3]~ có độ đẹp là 2;

Vậy độ đẹp hoàn hảo bằng: ~1+1+1+1+1+1+1+1+2+2 = 12~.

Subtasks

• Subtask 1: 20% số điểm có ~N \le 10~; ~1 \le A_i \le 10^5~; ~10^6 \le S \le 10^9~;
• Subtask 2: 20% số điểm có ~N \le 10^2~; ~A_i \le 10^3~; ~10 \le S \le 10^9~;
• Subtask 3: 30% số điểm có ~N \le 10^3~; ~A_i \le 10^4~; ~10 \le S \le 10^9~;
• Subtask 4: 30% số điểm còn lại không có ràng buộc gì thêm.