- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
مشرجب برای تولد ۶ سالگی خود یک نوار به طول \(n\) هدیه گرفته است که در هر کدام از خانههای آن یک عدد مثبت نوشته شده است.
در ابتدا تمامی خانههای این نوار آبی هستند. از آنجایی که مشرجب رنگ آبی را دوست ندارد، میخواهیم خانههای این نوار را برای او قرمز کنیم. میدانیم از نظر مشرجب میزان زیبایی یک بازه از نوار برابر با مجموع اعداد خانههای قرمز منهای اعداد خانههای آبی آن بازه است. همینطور میزان علاقه مشرجب به نوار برابر با بیشینه میزان زیبایی در میان تمام بازههای آن است.
میخواهیم یک به یک خانههای آبی را قرمز کنیم تا در نهایت تمام خانهها قرمز شوند. از آنجا که مشرجب هنوز به مدرسه نرفته است و محاسبه حاصل جمع و تفریق کمی برایش سخت است، از شما میخواهیم که بگویید پس از قرمز شدن هر خانه، میزان علاقه مشرجب به نوار در آن لحظه چقدر است.
ورودی
در خط اول ورودی عدد \(n\) آمده است. در خط دوم \(n\) عدد آمده است که عدد \(i\)-ام آن \(a_i\) یا همان عدد خانه \(i\)-ام ست. در خط سوم \(n\) عدد آمده است که ترتیب قرمز شدن خانهها را نمایش میدهد، اعداد این خط یک جایگشت از اعداد ۱ تا \(n\) هستند.
\[1 \le n \le 10^5\]
\[1 \le a_i \le 10^9\]
خروجی
در تنها خط خروجی باید \(n\) عدد چاپ کنید که عدد \(i\)-ام نشان میدهد میزان علاقه مشرجب به نوار بعد از مرحله \(i\)-ام چقدر است.
مثال
ورودی نمونه ۱
4
7 4 6 10
3 1 2 4
خروجی نمونه ۱
6 9 17 27
بعد از قرمز شدن خانه سوم نوار، زیباترین بازه از نظر مشرجب بازهی [۳,۳] است و زیبایی ۶ دارد. وقتی خانه اول نیز قرمز میشود، زیباترین بازه از نظر مشرجب بازه [۱,۳] است که زیبایی ۹ دارد.
ورودی نمونه ۲
10
4 2 7 6 4 2 6 3 1 7
8 3 1 6 2 7 10 4 5 9
خروجی نمونه ۲
3 7 9 9 13 14 20 32 40 42
ورودی نمونه ۳
10
75 98 33 45 27 57 91 54 42 59
8 6 5 9 1 2 7 10 3 4
خروجی نمونه ۳
54 57 84 96 96 184 366 425 491 581