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

شیرکاکائو

محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

آی مجری که به فکر بچه‌ها است، می‌خواهد به همه‌ی بچه‌ها شیرکاکائو بدهد. مشکل اینجاست که ظرفیت بچه‌ها متفاوت است. مثلا گابی مقدار خیلی زیادی شیرکاکائو احتیاج دارد تا خوشحال شود اما ببعی با یک لیوان شیرکاکائو بسیار خوشحال خواهد‌شد. در ضمن ممکن است بعضی ها اصلا شیرکاکائو نخورند. و یا مثلا مثل پسرخاله به جای خوردن شیرکاکائو، خودشان بروند و شیرکاکائوی بیشتری بخرند و به شیرکاکائو ها اضافه کنند. آی‌ مجری همه‌ی بچه‌ها را در یک خط نشانده‌است. بچه‌ی شماره‌ی $i$ م، $a_i$ لیوان شیرکاکائو میخورد. اگر $a_i$ صفر باشد یعنی آن فرد اصلا میل ندارد و اگر منفی بود یعنی آن بچه به شیر کاکائوها $-a_i$ لیوان اضافه میکند. روند شیرکاکائو خوردن به این شکل است که آی مجری به نفر اول مقداری شیرکاکائو(داخل یک پارچ بسیار بزرگ) می‌دهد. نفر اول به مقداری که می‌خواهد از آن برداشته یا اضافه می‌کند و بعد به نفر بعد می‌دهد. نفر دوم هم به همین شکل به نفر سوم می‌دهد و به همین شکل تا نفر آخر می‌روند. آی مجری می‌خواهد آن‌قدر شیرکاکائو به نفر اول بدهد که در طول مسیر به همه شیرکاکائو برسد. یعنی هیچ مرحله‌ای نباشد که یک نفر بخواهد یک مقدار شیرکاکائو بخورد و آن مقدار به دستش نرسیده باشد. همچنین آی مجری به تازگی به مشکل مالی برخورده و می‌خواهد کمترین مقدار ممکن شیرکاکائو بخرد و همه‌ی بچه‌ها را هم خوشحال کند.

ورودی🔗

در سطر اول ورودی عدد $n$ آمده‌است که نمایانگر تعداد بچه‌ها است. در سطر بعدی $n$ عدد آمده‌است که عدد $i$ م، نشان‌دهنده‌ی $a_i$ است.

$1 \le n \le 100\ 000$ $-10^9 \le a_i \le 10^9$

خروجی🔗

خروجی شامل یک عدد است که برابر کمینه مقدار(تعداد لیوان) شیرکاکائو که آی مجری باید بخرد تا همه‌ی بچه‌ها را خوشحال کند.

مثال🔗

ورودی نمونه ۱🔗

4
1 2 3 4

خروجی نمونه ۱🔗

ورودی نمونه ۲🔗

4
2 -3 2 2

خروجی نمونه ۲🔗

اگر آی مجری به اندازه‌ی دو لیوان به نفر اول بدهد، نفر اول هر دو لیوان را می‌خورد و پارچ خالی را به نفر دوم می‌دهد. نفر دوم سه لیوان به آن اضافه می‌کند و به سومی می‌دهد. سومی دو لیوان از سه لیوان موجود در پارچ را خورده و به نفر چهارم می‌دهد. نفر آخر می‌خواهد دولیوان شیرکاکائو بخورد ولی در پارچ یک لیوان موجود است. برای همین باید حداقل سه لیوان شیرکاکائو در اول کار در پارچ باشد.