Problem
नन्ही पेट्या को डॉट्स बहुत पसंद हैं। हाल ही में, उसकी माँ ने उसे n अंक दिए जो रेखा OX पर स्थित है। पेट्या ने सोचा कि वह तीन अलग-अलग बिंदुओं को कितने तरीकों से चुन सकता है ताकि चयनित बिंदुओं में से दो सबसे दूर के बीच की दूरी d से अधिक न हो।
ध्यान दें कि चयनित तिकड़ी में अंकों का क्रम मायने नहीं रखता।
इनपुट
पहली पंक्ति में दो पूर्णांक हैं: n और d (1 ≤ n ≤ 105; 1 ≤ d ≤ 10< समर्थन>9). अगली पंक्ति में n पूर्णांक x1, x2, ..., xn, modulo 109 — पेट्या को दिए गए अंकों के एक्स-निर्देशांक।
यह गारंटी है कि इनपुट में बिंदुओं के निर्देशांक सख्ती से बढ़ रहे हैं।
आउटपुट
एक पूर्णांक प्रिंट करें — बिंदुओं के त्रिगुणों की संख्या जहां दो सबसे दूर के बिंदुओं के बीच की दूरी d से अधिक नहीं है।
कृपया C++ में 64-बिट संख्याओं को पढ़ने या लिखने के लिए %lld विनिर्देशक का उपयोग न करें। Cin, cout स्ट्रीम या %I64d स्पेसिफायर का उपयोग करने की अनुशंसा की जाती है।
<तालिका सीमा = "1" सेलपैडिंग = "1" सेलस्पेसिंग = "1" शैली = "चौड़ाई: 500 पीएक्स">
<शरीर>
| इनपुट |
आउटपुट |
<टीडी>
4 3
1 2 3 4
4 |
<टीडी>
4 2
-3 -2 -1 0
2 |
<टीडी>
5 19
1 10 20 30 50
1 |
पहले उदाहरण में, कोई तीन अलग-अलग बिंदु हमारे लिए उपयुक्त हैं।
दूसरे उदाहरण में, केवल 2 त्रिक हमारे लिए उपयुक्त हैं: {-3, -2, -1} और {-2, -1, 0}।
तीसरे उदाहरण में, एक तिहरा हमारे लिए उपयुक्त है: {1, 10, 20}।