نقاط روی یک خط
Problem
پتیا کوچولو عاشق نقطه هاست. اخیراً، مادرش به او n امتیاز داده است که روی خط OX قرار دارد. پتیا تعجب کرد که از چند راه می تواند سه نقطه مختلف را انتخاب کند تا فاصله بین دو دورترین نقطه انتخاب شده از d تجاوز نکند.
توجه داشته باشید که ترتیب امتیازها در سه نفر انتخاب شده مهم نیست.
ورودی
خط اول شامل دو عدد صحیح است: n و d (1 ≤ n ≤ 105; 1 ≤ d ≤ 10< sup>9). خط بعدی شامل n عدد صحیح x1، x2، ...، xn، مدول بیش از 109 — مختصات x از نقاط داده شده به پتیا.
تضمین می شود که مختصات نقاط ورودی به شدت در حال افزایش است.
خروجی
چاپ یک عدد صحیح — تعداد سه گانه نقاطی که فاصله بین دو دورترین نقطه از d تجاوز نمی کند.
لطفاً از تعیین کننده %lld برای خواندن یا نوشتن اعداد 64 بیتی در C++ استفاده نکنید. توصیه می شود از cin، جریان های cout یا مشخص کننده %I64d استفاده کنید.
<بدن>
| ورودی |
خروجی |
|
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}.