KANGAROO

Đề bài

Nhân dịp Kangaroo (Gọi là Ri cho ngắn) con tròn 1 tuổi, Ri cha dẫn cậu lên thành phố Sydney xinh đẹp với những tòa nhà cao chót vót và thách đố cậu ta với tập nhảy những bước dễ thương.

Thành phố có \(n\) tòa nhà được xây dựng thẳng tắp từ trái sang phải, có độ cao lần lượt là \(a_1, a_2, ..., a_n\). Ri cha chọn ba tòa nhà để cậu Ri nhảy. Tuy nhiên, để có thể có một bài huấn luyện hiệu quả, các bước nhảy phải thỏa mãn yêu cầu sau: từ tòa nhà thứ \(i\) đến \(j\), sau đó đến \(k\) (với \(1 \leq i < j < k \leq n\)), thỏa mãn:

• \(a_i < a_j < a_k\)
• \(a_i + a_j + a_k \leq w\)

Hỏi có bao nhiêu bộ ba tòa nhà \((i, j, k)\) thỏa mãn các điều kiện trên?

Dữ liệu vào

• Dòng đầu chứa hai số nguyên dương \(n, w\) (\(1 \leq n \leq 10^4\), \(1 \leq w \leq 10^9\))
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_i\) (\(1 \leq a_i \leq 10^9\))

Dữ liệu ra

• Một dòng duy nhất là kết quả bài toán là số bộ ba thỏa mãn điều kiện.

Giới hạn

Sample Input

8 16
4 2 1 6 2 1 9 8

Sample Output

8

Giải thích

Các bộ ba thỏa mãn điều kiện là:

• \((1, 4, 8)\): \(4 < 6 < 8\) và \(4+6+8 = 18 > 16\) ❌
• \((2, 4, 8)\): \(2 < 6 < 8\), \(2+6+8 = 16\) ✅
• \((3, 4, 8)\): \(1 < 6 < 8\), \(1+6+8 = 15\) ✅
• … và 6 bộ ba khác thỏa mãn, tổng cộng 8 bộ ba hợp lệ.