Bài 2: Tuyến đường Tẩu thoát

• Két sắt đã mở, Pitomon lấy được tài liệu nhưng còi báo động đã reo vang. Hành lang tẩu thoát trước mắt là một đường thẳng gồm \(N\) khu vực liên tiếp, mỗi khu vực có một mức độ nguy hiểm (tương ứng với số lượng lính canh) được biểu diễn bằng mảng \(A\) gồm \(N\) phần tử nguyên dương.

• Để thoát thân, Pitomon cần chọn ra một đoạn đường liên tiếp duy nhất bắt đầu từ khu vực \(L\) và kết thúc ở khu vực \(R\) (\(1 \le L \le R \le N\)) để bứt tốc chạy trốn. Nhờ có "Bảo bối Tàng hình", cậu có thể đi qua khu vực đông lính canh nhất trong đoạn đường vừa chọn mà không tốn sức. Do đó, lượng thể lực tiêu hao cho toàn bộ chặng đường từ \(L\) đến \(R\) sẽ bằng tổng lính canh trong đoạn trừ đi số lính canh lớn nhất trong đoạn đó.

• Tổng thể lực của Pitomon hiện tại chỉ có giới hạn là \(S\). Do đó, đoạn đường \((L, R)\) được chọn phải an toàn, tức là lượng thể lực tiêu hao không được vượt quá \(S\):
  \(\sum_{i=L}^{R} A_i - \max_{i=L}^{R}(A_i) \le S\)

• Pitomon muốn cân nhắc mọi bến đỗ an toàn có thể. Nói cách khác, hãy tính xem có bao nhiêu cách chọn một cặp chỉ số \((L, R)\) thỏa mãn điều kiện trên. Vì đang bận né lính canh nên không rảnh gõ phím, các bạn hãy dùng tài năng lập trình của mình để đếm số cặp \((L, R)\) giúp Pitomon nhé!!!!!

Input

• Dòng đầu tiên chứa 2 số nguyên N và S (1 <= N <= 100000, 0 <= S <= 10^14) mô tả số lượng khu vực và tổng thể lực giới hạn của Pitomon.
• Dòng tiếp theo chứa N số nguyên dương \(A_1, A_2, ..., A_N\) (1 <= \(A_i\) <= 10^9) biểu diễn mức độ nguy hiểm của từng khu vực.

Output

• Một dòng duy nhất chứa 1 số nguyên là số lượng cặp chỉ số (L, R) thỏa mãn điều kiện tẩu thoát.

Scoring

• Subtask 1: có 30% số điểm với N <= 1000
• Subtask 2: có 30% số điểm với N <= 100000 và S = 0
• Subtask 3: có 40% số điểm với N <= 100000 và S <= 10^14

Sample Input 1

4 3
3 1 2 4

Sample Output 1

9

Sample Input 2

3 0
5 2 3

Sample Output 2

3

Giải thích

Ở ví dụ thứ nhất, có 9 đoạn đường (L, R) thỏa mãn lượng thể lực tiêu hao <= 3:

- Các đoạn độ dài 1: (1,1), (2,2), (3,3), (4,4) tiêu hao 0 thể lực.
- Đoạn (1,2) gồm [3, 1]: tiêu hao (3 + 1) - 3 = 1 <= 3.
- Đoạn (2,3) gồm [1, 2]: tiêu hao (1 + 2) - 2 = 1 <= 3.
- Đoạn (3,4) gồm [2, 4]: tiêu hao (2 + 4) - 4 = 2 <= 3.
- Đoạn (1,3) gồm [3, 1, 2]: tiêu hao (3 + 1 + 2) - 3 = 3 <= 3.
- Đoạn (2,4) gồm [1, 2, 4]: tiêu hao (1 + 2 + 4) - 4 = 3 <= 3.
Riêng đoạn (1,4) gồm [3, 1, 2, 4] tiêu hao (3 + 1 + 2 + 4) - 4 = 6 > 3 nên không thỏa mãn.