+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- دزد با مهارت، به طبقه‌ی آخر رسید. او در آنجا با یک گاوصندوق مواجه شد که شنیده بود که پر از تیله است. اما او در اینجا با یک سد دفاعی محکم مواجه شد. پروفسورباقر که مسئول طراحی سیستم دفاعی فروشگاه بود(و خیلی هم ناشی بود)، موقع طراحی طبقه‌ی آخر، برای اینکه دزدی نتواند به گاوصندوق راه پیدا کند، بر روی زمین تیله ریخته بود تا هر کس بخواهد به گاوصندوق برسد، روی این تیله‌ها لیز بخورد و سپس به زمین نیز (چی؟) بخورد. وقتی دزد به طبقه‌ی آخر رسید، متوجه شد که بر روی زمین مقدار زیادی تیله ریخته شده است و او هم که به دزدی تیله آمده بود؛ پس شروع کرد به جمع کردن تیله‌های روی زمین. او تیله ها را در ‌$n$ کیسه ریخت. بعد از آن از ساختمان خارج شد و به پیش عمو (که بسیار پول پرست است) رفت تا کیسه‌هایش را بفروشد اما عمو در حال پرستش بود و در آن لحظه نمی‌توانست به دیدار دزد بیاید. برای همین دزد به اتاق انتظار رفت تا منتظر عمو بماند. دزد کیسه‌ها را بر روی یک میز در یک ردیف چید و منتظر ماند تا عمو بیاید. او کیسه‌ها را از یک تا $n$ به ترتیب از چپ به راست نام گذاری کرد و می‌داند که در کیسه‌ی $i$، $a_i$ تیله وجود دارد. در همین حین ناگهان نکته‌ای به ذهن دزد رسید: عمو همیشه موقع خرید تیله، یک بازه‌ی $d$ تایی پشت سر هم از کیسه‌ها را انتخاب می‌کند و اگر تعداد تیله ها در این $d$ کیسه زوج بود، پولش را می‌دهد و گرنه با لگد دزد را از دفترکارش بیرون می‌اندازد(بالاخره عمو که نمی‌تواند خدایش را به راحتی به دست دزد بدهد که.خدایش است ها علف خرس که نیست). به همین دلیل دزد مجبور است که تعداد تیله‌ها در برخی کیسه‌ها را تغییر دهد تا اگر عمو هر بازه‌ی $d$ تایی پشت سر هم از کیسه‌ها را انتخاب کرد، تعداد تیله‌ها در مجموع این کیسه ها زوج باشد. خوشبختانه دزد تعدادی تیله در جیبش دارد. او در یک عملیات می‌تواند یک کیسه را انتخاب کند و دقیقا یک تیله به آن اضافه کند. به او بگویید که کمینه‌ی تعداد عملیات برای این که کیسه‌ها را مطابق میل عمو کند چقدر است. # ورودی در خط اول ورودی به ترتیب $n$ و $d$ آمده است که $n$ نمایانگر تعداد کیسه‌ها و $d$ نمایانگر اندازه‌ی بازه‌‌ی پشت سر همی از کیسه‌ها است که عمو انتخاب می‌کند و تعداد تیله‌ها در مجموع این $d$ کیسه باید زوج باشد. سپس در خط بعد $n$ عدد آمده است که عدد $i$ ام نمایانگر تعداد تیله‌ها در کیسه‌ی $i$ است. $$ 1 \le d \le n \le 1\ 000\ 000 $$ $$ 0 \le a_i \le 1\ 000\ 000\ 000$$ # خروجی در تنها سطر خروجی کمترین تعداد عملیاتی را بنویسید که دزد باید انجام دهد. # مثال ## ورودی نمونه ``` 5 3 1 3 0 5 2 ``` ## خروجی نمونه ``` 1 ``` توضیح نمونه: تنها کافیست که دزد یک تیله به کیسه‌ی آخر بیافزاید.

حل سؤال در بانک سؤالات