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

---

پس از امتحان میان‌ترم هندسه، این‌بار کاراکتر اصلی که به تازگی خوی مبارزه با دانش‌آموز گرفته است سعی دارد از طریق امتحان پایان‌ترم هندسه دانش‌آموزان بی‌گناهش (که آن‌ها را با نام کاراکتر‌های کمکی می‌شناسیم) را مورد آزار قرار دهد.

کاراکتر کمکی ۱ و کاراکتر کمکی ۲ که هر دو به شدت امتحانشان را خراب کردند به فکر راهی برای انتقام افتادند.

انتقام از معلم هندسه‌ی نابکارشان ناشدنی به‌نظر می‌رسد پس به این نتیجه رسیدند که لااقل از برگه‌های امتحانی انتقام بگیرند تا گوشه‌ای از عقده‌ی گوشه‌ی دلشان باز شود. همان‌طور که می‌دانید آن‌ها تنها نیستند و با $n - 2$ دانش‌آموز فلک زده‌ی دیگر دست به یکی کردند تا در روزی مشخص پس از مدرسه جمع شوند و $n$ برگه‌ی امتحانی‌شان را در یک جمع دانش‌آموزی مورد محاکمه قرار بدهند. آن‌ها در دادگاه دانش‌آموزی بین خودشان حکمی برای این برگه‌ها صادر کردند که کاراکتر کمکی ۱ و کاراکتر کمکی ۲ مامور اجرای این حکم هستند. برای هیجان انگیزتر شدن اجرای حکم قضایی، کاراکتر کمکی ۱ و کاراکتر کمکی ۲ تصمیم گرفتند حکم را به یک بازی بین خودشان تبدیل کنند.

هدف بازی مجازات همه‌ی $n$ برگه‌ی امتحانی است و قرار است به ترتیبی این مجازات توسط دو بازیکن بازی یعنی کاراکتر کمکی ۱ و کاراکتر کمکی ۲ انجام شود. قوانین انجام بازی به شرح زیر است:

• در ابتدا $n$ برگه‌ی امتحانی باید در یک ردیف قرار بگیرند.

• هر برگه‌ی امتحانی با توجه به مقدار سختگیری کاراکتر اصلی در تصحیح آن باید مجازات شود، مجازات به این ترتیب است که یک نفر از بین کاراکتر کمکی ۱ و کاراکتر کمکی ۲ به سمت برگه‌ی $i$ام با میزان نفرت $a_i$ شلیک می‌کند. (دقت کنید ممکن است میزان نفرت مجازات منفی باشد)

• بازی نوبتی است و چون کاراکتر کمکی ۱ از لحاظ سنی (و نه از لحاظ عقلی) بزرگتر است، بازی را شروع می‌کند.

• در هر مرحله بازیکنی که نوبتش است مختار است یکی از برگه‌ها را به دلخواه به عنوان هدف انجام مجازات انتخاب کند، وقتی برگه‌ای انتخاب شود تمام برگه‌های با شماره‌ی کمتر از آن برگه خود بخود با دیدن مجازات برگه‌ی مجازات شده، مجازات می‌شوند، به عبارت دیگر اگر $i$امین برگه برای مجازات انتخاب شود تمام برگه‌های مجازات‌نشده‌ی با شما‌ره‌ی کم‌تر از $i$ هم مجازات می‌شوند. (هیچ برگه‌ای دوبار مجازات نمی‌شود)

• مجموع میزان‌ نفرت‌های مفید شلیک‌های انجام شده توسط هر فرد امتیاز فرد در بازی را مشخص می‌کند. مجموع‌ میزان نفرت‌های مفید شلیک‌ها یعنی مجموع میزان نفرت لازم برای مجازات تمام برگه‌های انتخاب‌شده توسط هر فرد و نه تمام برگه‌های مجازات شده توسط فرد.

همان‌طور که قبلا هم اشاره شد در هوش کاراکتر کمکی ۱ و کاراکتر کمکی ۲ شکی نیست، پس یقین داریم بهترین انتخاب‌ها را برای کسب بیشترین مجموع مجازات انجام خواهند داد.

در خروجی دو چیز از شما می‌خواهیم:

• مشخص کنید چه کسی می‌برد. (کسی که امتیاز بیشتری کسب کند برنده‌ی بازی است)

• اگر مطلوب علاوه بر بردن بازی، با بیشینه اختلاف بردن باشد، شخصی که می‌برد (در صورتی که بازی به مساوی کشیده نشود) حداکثر با چه اختلاف تضمین‌شده‌ای برنده‌ی بازی می‌شود؟

ورودی

در خط اول ورودی عدد طبیعی $n$ داده می‌شود.

در خط بعدی ورودی $n$ عدد طبیعی داده می‌شود که $i$امین عدد نشان‌دهنده میزان نفرت لازم برای مجازات برگه‌ی $i$ام است.

$$1 \leq n \leq 1 \ 000 \ 000$$ $$|a_i| \leq 1 \ 000 \ 000 \ 000$$

خروجی

در صورتی که بازی با بازی هوشمندانه‌ی دوطرف به مساوی ختم شود، mosavi را چاپ کنید، در صورتی که کاراکتر کمکی ۱ بازی را ببرد، < اختلاف > :karakter e komaki_1 را در خروجی چاپ کنید و در صورتی که کاراکتر کمکی ۲ بازی را ببرد، < اختلاف > :karakter e komaki_2 را در خروجی چاپ کنید.

مثال

ورودی نمونه ۱

6
1 2 100 4 5 99

خروجی نمونه ۱

karakter e komaki_1: 99

ورودی نمونه ۲

2
-10 -10

خروجی نمونه ۲

mosavi

ورودی نمونه ۳

1
-1

خروجی نمونه ۳

karakter e komaki_2: 1

توضیح

در مثال اول همان اولین مجازات برای کاراکتر کمکی ۱ کافی است تا بازی را با بیش‌ترین اختلاف ببرد و با انتخاب برگه‌ی ۶ام بازی را با ۹۹ امتیاز اختلاف، به نفع خودش پایان دهد.

در مثال دوم اگر در مجازات اول کاراکتر اصلی ۱ برگه‌ی شماره‌ی ۲ را انتخاب کند بازی را با ۱۰ امتیاز اختلاف می‌بازد، پس برگه‌ی شماره‌ی ۱ را انتخاب می‌کند و بازی مساوی می‌شود.

در مثال سوم تنها انتخاب کاراکتر کمکی ۱ برای انتخاب کردن برگه‌ی شماره‌ی ۱ است، پس آن را انتخاب می‌کند و بازی به نفع کاراکتر کمکی ۲ با ۱ امتیاز اختلاف تمام می‌شود.