Problem

5 /11


مدينة تشي

Problem

يوجد في وسط مدينة تشي شارع للمشاة - أحد أكثر الأماكن شعبية للمشي لسكان المدينة. إنه لأمر ممتع للغاية أن تمشي على طول هذا الشارع ، لأنه توجد آثار مضحكة على طول الشارع.
& nbsp؛
ماشا ، فتاة من مدينة تشي ، تحب طفلين من مدرستها ، ولا يمكنها الاختيار بينهما. لاتخاذ قرارها النهائي ، قررت مواعدة كلا الصبيان في نفس الوقت. تريد ماشا اختيار نصب تذكاري في شارع المشاة ، حيث سينتظرها الأولاد بالقرب منها. في الوقت نفسه ، تريد اختيار مثل هذه المعالم حتى لا يرى الأولاد بعضهم البعض. تعرف ماشا أنه بسبب الضباب ، لن يرى الأولاد بعضهم البعض إلا إذا كانوا على مسافة لا تزيد عن r أمتار.
& nbsp؛
تساءل ماشا عن عدد الطرق المتاحة لاختيار نصبين مختلفين للتعارف.
& nbsp؛
إدخال
يحتوي السطر الأول على عددين صحيحين n و r (2 & lt؛ = n & lt؛ = 300000، 1 & lt؛ = r & lt؛ = 10 9 ) - عدد المعالم والحد الأقصى للمسافة التي يمكن للفتيان يرى بعضنا البعض.
يحتوي السطر الثاني على n أعداد موجبة d1 ... dn ، حيث di هي المسافة من النصب i إلى بداية الشارع. تقع جميع المعالم الأثرية على مسافات مختلفة من بداية الشارع. الآثار مدرجة بترتيب زيادة المسافة من بداية الشارع (1 & lt؛ = d1 & lt؛ d2 & lt؛ ... & lt؛ dn & lt؛ = 10 9 ).
& nbsp؛
الإخراج
اطبع رقمًا واحدًا - عدد طرق اختيار نصب تذكاري للتاريخ. نبسب ؛
أمثلة <الجسم>
# إدخال الإخراج الشرح
1
4 4
1 3 5 8
2 في المثال أعلاه ، يمكن لماشا اختيار المعالم 1 و 4 أو المعالم 2 و 4.
& nbsp؛

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!