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

---

در یک رستوران غذاها را به صورت سلف سرویس در یک ردیف قرار می‌دهند. میزان کالری هر غذا را می‌توان با یک عدد صحیح نشان داد. (این عدد می‌تواند منفی باشد.)

در واقع می‌توان وضعیت کالری‌ها را به صورت یک دنباله از اعداد صحیح \(a_1, a_2, \dots, a_n \,\) در نظر بگیریم. که \(a_i\) کالری غذای \(i\)ام را نشان می‌دهد.

در یک روز \(k\) نفر وارد رستوران می‌شوند و می‌خواهند این غذاها را بخورند. هر کس یک بازه از این دنباله را انتخاب می‌کند و همه‌ی غذاهای این بازه را می‌خورد. هر کس باید یک بازه ناتهی انتخاب کند و نباید بازه هیچ دو نفری اشتراک داشته باشد.

صاحب رستوران می‌خواهد بداند حداکثر کالری که این \(k\) نفر می‌توانند بخورند را پیدا کند. اما چون نمی‌داند مقدار \(k\) چقدر است؛ از شما می‌خواهد به‌ازای همه‌ای اعداد طبیعی از \(1\) تا \(n\) این مقدار را محاسبه کنید.

ورودی

در سطر اول ورودی، عدد صحیح و مثبت \(n\) آمده که تعداد غذاها را نشان می‌دهد. \[1 \leq n \leq 300 \, 000\]

در سطر دوم ورودی، \(n\) عدد صحیح که با یک فاصله از هم جداشده‌اند آمده است که عدد \(i\)ام آن برابر \(a_i\) بوده و نشان‌دهنده‌ی میزان کالری غذای \(i\)ام است.

\[-10^9 \leq a_i \leq 10^9\]

خروجی

خروجی \(n\) سطر دارد، در سطر \(k\)ام، حداکثر میزان کالری که با آمدن \(k\) نفر به رستوران می‌توان بدست آورد را محاسبه کنید.

مثال‌ها

ورودی نمونه ۱

3
4 5 1

خروجی نمونه ۱

10
10
10

ورودی نمونه ۲

5
-1 -2 -3 -4 -5

خروجی نمونه ۲

-1
-3
-6
-10
-15

ورودی نمونه ۳

8
1 3 -8 3 4 1 -9 7

خروجی نمونه ۳

8
15
19
19
19
19
11
2