Module: دو اشاره گر


Problem

5 /11


شهر چه

Problem

در مرکز شهر چه یک خیابان عابر پیاده وجود دارد - یکی از محبوب ترین مکان ها برای پیاده روی ساکنان شهر. قدم زدن در این خیابان بسیار لذت بخش است، زیرا n بنای تاریخی خنده دار در امتداد خیابان وجود دارد.
 
ماشا، دختری از چه، از دو پسر مدرسه اش خوشش می آید و نمی تواند بین آنها تصمیم بگیرد. او برای تصمیم نهایی خود تصمیم گرفت همزمان با هر دو پسر قرار بگذارد. ماشا می خواهد دو بنای تاریخی را در خیابان عابر پیاده انتخاب کند که در نزدیکی آن پسران منتظر او باشند. در عین حال او می خواهد چنین بناهایی را انتخاب کند تا پسرها یکدیگر را نبینند. ماشا می داند که به دلیل مه، پسرها فقط در صورتی همدیگر را می بینند که بیش از یک متر فاصله نداشته باشند.
 
ماشا تعجب کرد که چند راه برای انتخاب دو بنای تاریخی مختلف برای دوستیابی وجود دارد.
 
ورودی
خط اول شامل دو عدد صحیح n و r است (2<=n<=300 000، 1<=r<=109) - تعداد بناهای تاریخی و حداکثر فاصله ای که پسرها می توانند یکدیگر را ببینید.
خط دوم شامل n عدد مثبت d1 ... dn است که di فاصله ای است از i امین بنای تاریخی تا ابتدای خیابان. همه بناهای تاریخی در فواصل مختلف از ابتدای خیابان قرار دارند. بناهای تاریخی به ترتیب افزایش فاصله از ابتدای خیابان فهرست شده اند (1<=d1 <d2< ... < dn<=109).
 
خروجی
چاپ یک عدد - تعداد روش‌های انتخاب دو بنای تاریخی برای قدمت.
 
نمونه‌ها
<سر> <بدن>
# ورودی خروجی توضیح
1
4 4
1 3 5 8
 2 در مثال بالا، ماشا می تواند بناهای 1 و 4 یا بناهای 2 و 4 را انتخاب کند.
 

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!