+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۱۰۰ مگابایت ------------------------ کشوری $n$ نفر با میزان سرمایهٔ $a_1$ تا $a_n$ دارد. سرمایهٔ هرکس می‌تواند عددی مثبت یا منفی (به‌معنای مقروض بودن) باشد. به یک شماره‌دهی از ۱ تا $n$ به این افراد، یک **جامعه** می‌گوییم. جامعه‌شناسان پس از بررسی جوامع مختلف به این نتیجه رسیدند که در هر جامعه، مردم تنها به اختلاف طبقاتی خود با افراد مجاور خود اهمیت می‌دهند. بنابراین شاخصی به‌عنوان *پتانسیل اعتراضی* تعریف کردند که هرچه مقدار این شاخص برای یک جامعه کم‌تر باشد، آن جامعه پایدارتر است. شاخص پتانسیل اعتراضی یک جامعهٔ دلخواه $m$ نفری از فرمول زیر محاسبه می‌گردد: $$P_E = \sum_{i = 1}^{m-1} |F_{i+1} - F_i|$$ که $F_i$ میزان سرمایهٔ نفر شمارهٔ $i$ این جامعه است. شما به‌عنوان حاکم این کشور، می‌توانید با دادن یک حکم، دو فرد با جایگاه **مجاور** در جامعه‌ را جابه‌جا کنید و این کار را ان‌قدر تکرار کنید تا به جامعهٔ آرمانی (جامعه‌ای با $P_E$ کمینه) برسید. حداقل پتانسیل اعتراضی ممکن چند است؟ با دادن حداقل چند حکم می‌توان به آن رسید؟ # ورودی در خط اول ورودی عدد $n$ — تعداد اعضای کشور آمده‌است. در خط بعدی $n$ عدد آمده که سرمایهٔ این افراد را نشان می‌دهد. # خروجی در خروجی باید ابتدا مقدار $P_E$ برای جامعهٔ آرمانی را چاپ کنید و سپس بگویید به چند حکم جابه‌جایی برای رسیدن به این جامعه نیاز داریم. ## محدودیت‌ها در ۵۰٪ تست‌ها، $n \le 1000$ و در تمامی تست‌ها $n \le 100000$ است. ### ورودی نمونه ۱ ``` 5 12 -3 2 8 1 ``` ### خروجی نمونه ۱ ``` 15 4 ``` ### ورودی نمونه ۲ ``` 4 3 1 2 4 ``` ### خروجی نمونه ۲ ``` 3 2 ```

+ محدودیت زمان: ۱.۵ ثانیه + محدودیت حافظه: ۱۰۰ مگابایت ------------------------ با وجود تمهیدات اندیشیده شده برای کمینه کردن پتانسیل اعتراضی به‌وسیلهٔ کنترل اختلاف طبقاتی افراد مجاور، باز هم به‌دلیل کشورداری نامناسب شما تعدادی معترض به حکومت پدید آمده‌اند. آن‌ها به‌طور کلی عضو دو جناح $a$ یا $b$ شده‌اند و طبق تحقیقات وزارت اطلاعات کشور (واک)، تعداد آن‌ها $n$ تاست. شما طبق یک حرکت اصلاحاتی، تمامی این افراد را دستگیر کرده‌اید و حال می‌خواهید تعدادی‌شان را بکشید. لذا با ذکر جملهٔ "Let's play a game"، بازی را شروع می‌کنید. بازی شما این‌گونه است که افراد را در یک صف کنار هم قرار می‌دهید و به هرکدام لباسی با شمارهٔ از ۱ تا $n$ می‌پوشانید. با شروع از سمت چپ، هرگاه یک معترض وابسته به حزب $a$ دیدید و اولین نفر زنده در سمت راست‌ش نیز یک معترض حزب $b$ بود، هر دو را تیربار کرده و شمارهٔ پیراهن آن دو را یادداشت می‌کنید. آن‌قدر این کار را تکرار می‌کنید که دیگر دو فرد با چنین شرایطی وجود نداشته باشند و ضمن یادداشت ترتیب افراد باقی‌مانده، آن‌ها را به حبس ابد محکوم می‌کنید. فردای آن روز هم به‌منظور نشان دادن اقتدار و هم‌چنین عطوفت‌تان، لیست شماره‌های اعدام شده و هم‌چنین ترتیب افراد بازگشته از مرگ را در روزنامه‌های کثیرالانتشار چاپ می‌کنید. # ورودی در تنها خط ورودی، نام حزب منسوب به افراد حاضر در صف آمده‌است. # خروجی در خط اول ورودی رشته مربوط به افراد باقی‌مانده را چاپ کنید. در خط دوم تعداد اعدام‌ها را چاپ کنید و در خطوط بعد، به ازای هر اعدام شماره افراد اعدام شده را (به ترتیب) چاپ کنید. ## محدودیت‌ها در ۵۰٪ تست‌ها $n \le 2000$ و در تمام تست‌ها $n \le 10^6$ است. ### ورودی نمونه ``` bbaabaaab ``` ### خروجی نمونه ``` bbaaa 2 4 5 8 9 ``` ### ورودی نمونه ``` baabbab ``` ### خروجی نمونه ``` b 3 3 4 2 5 6 7 ```

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۱۰۰ مگابایت ------------------------ حتما تاکنون متوجه شده‌اید که آقای حاکم بسیار به بازی کردن علاقه دارد. او به‌مناسبت نزول باران‌های اردی‌بهشت می‌خواهد به $n$ نفر مسئولین حکومتی پاداش بدهد. بنابراین یک بازی ترتیب می‌دهد: در هر نوبت به یک نفر از مسئولین یک کیسه با $n-1$ سکه داده می‌شود که مسئول پخش آن‌هاست. سپس مسئول انتخاب شده به هرکدام از دیگر مسئولین یک سکه می‌دهد (خودش چیزی برنمی‌دارد). هیچ‌کدام از این $n$ نفر دوست ندارند در آخر بازی کم‌تر از حدی پاداش گرفته باشند و این حد برای نفر $i$م برابر $A_i$ است. حال حاکم می‌خواهد بداند مسئولین حداقل چند نوبت باید بازی کنند تا همه‌شان حداقل به‌میزان مطلوب پاداش دریافت کرده باشند و راضی باشند. # ورودی در خط اول عدد $n$ — تعداد مسئولین شایستهٔ تقدیر آمده‌است. در خط بعدی $n$ عددِ $A_1$ تا $A_n$ آمده‌است که $A_i$ حداقل تعداد سکه‌ای‌ست که مسئول $i$م دوست دارد پاداش بگیرد. # خروجی پاسخ پرسش حاکم را بیابید — حداقل چند نوبت باید بازی انجام شود. ## محدودیت‌ها در ۵۰٪ تست‌ها $n \leq 2000$ و $\Sigma A_i \leq 2000$ و در کل تست‌ها $n \le 10^5$ و $0 \le A_i \le 10^9$ است. ### نمونهٔ ورودی ۱ ``` 3 3 2 2 ``` ### نمونهٔ خروجی ۱ ``` 4 ``` ### نمونهٔ ورودی ۲ ``` 4 2 2 2 2 ``` ### نمونهٔ خروجی ۲ ``` 3 ```