+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------------- یک روز یک خری متعلق به مناطق بیابانی به استادیوم فوتبال رفت و به دلیل خرارت(خر بودن) به جای سکوها به داخل زمین رفت. سپس او با دیدن چمن به سر شوق آمد و دیدن هزاران انسان که دور او بودند دو برابر او را ذوق زده کرد؛ احساس کنسرت به او دست داد و تصمیم گرفت که برایشان بخواند(عرعر کند)! او از موسیقی و ریتم چیزی حالی‌اش نبود اما برای اینکه عرعرش ریتمیک باشد تصمیم گرفت که بین عرعرهایش فاصله‌ی مشخصی بیندازد. برای همین او یک عدد $a$ و یک عدد $b$ انتخاب کرد و تصمیم گرفت که اینگونه بخواند: او در ثانیه‌ی ۰ به مردم اعلام می‌کند که قرار است یک آهنگ درخواستی برایشان بخواند. سپس $a$‌ ثانیه صبر می‌کند و در ثانیه‌ی $a$ عرعر اول را سر می‌دهد. سپس $b$‌ ثانیه صبر می‌کند و در ثانیه‌ی $a+b$ عرعر دوم را سر می‌دهد. بعد دوباره $a$ ثانیه صبر می‌کند و در ثانیه‌ی $2 \times a + b$ عرعر می‌کند. سپس $b$ ثانیه صبر می‌کند و ... او از اول با خودش قرار گذاشته بود که بیشتر از $l$ بار عرعر نکند. (حنجره‌اش طاقت بیشتر از این مقدار را نمی‌کشد) حالا او $l$‌ بار عرعر کرده است و برایش سوال است که از زمانی که به مردم اعلام کرد که قرار است برایشان بخواند تا الان که آخرین عرعر را سر داده است چند ثانیه گذشته است. او خر است و از شما می‌خواهد که به سوالش جواب بدهید. # ورودی در تنها سطر ورودی به ترتیب سه عدد $a$ و $b$ و $l$‌ می‌آید که به ترتیب نمایانگر زمان‌های صبر بین عرعرها و تعداد عرعرها می‌باشند. $$ 1 \le a,b,l \le 1000 $$ # خروجی در تنها خط خروجی زمان آخرین عرعر را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 1 1 1 ``` ## خروجی نمونه ۱ ``` 1 ``` ## ورودی نمونه ۲ ``` 3 4 5 ``` ## خروجی نمونه ۲ ``` 17 ``` ## ورودی نمونه ۳ ``` 10 3 2 ``` ## خروجی نمونه ۳ ``` 13 ```

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

* محدودیت زمان:‌ ۳ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ------------------------------ در هر خانه از یک جدول $n$ در $m$ یک دومینوی ایستاده قرار داده شده است. هر دومینو یا عمودی است یا افقی (دومینوهای عمودی فقط در جهت بالا یا پایین می‌افتد و دومینوهای افقی فقط در جهت چپ یا راست). وقتی یک دومینو در یک جهت می‌افتد دومینوی موجود در خانه‌ی بعدی (در همان جهت) نیز اگر از نظر عمودی و افقی بودن مانند این دومینو باشد می‌افتد (دومینوها فقط در شرایط گفته شده بر روی دومینوهای دیگر تاثیر می‌گذارند). می‌خواهیم تعدادی دومینو را بیاندازیم به طوری که همه‌ی دومینوها بیافتند. حداقل چند دومینو را باید بیاندازیم؟ # ورودی در خط اول ورودی دو عدد $ n $ و $ m $ آمده است که تعداد سطرها و ستون‌های جدول را نشان می‌دهند. در $ n $ خط بعدی در هر خط، $ m $ کاراکتر آمده که هر کدام نشان دهنده‌ی وضعیت یک دومینو است (`|` برای دومینوهای افقی و `-` برای دومینوهای عمودی) $$1 \le n, m \le 3000$$ # خروجی جواب مسئله را در یک خط چاپ کنید. # مثال ## ورودی نمونه ``` 3 3 ||| ||- ||- ``` ## خروجی نمونه ``` 4 ``` در ورودی نمونه سه دومینوی واقع در ستون اول را به سمت راست و دومینوی واقع در ستون سوم و سطر دوم را به سمت پایین می‌اندازیم.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- «مِسِریکس» از گرمایش جهانی به ستوه آمده و قصد دارد از خلاّقیّتش در زمینه‌ی بحران محیط زیست استفاده کند؛ امّا... به تازگی پلیس با خبر شده که قرار است حمله‌ای تروریستی به شهر بشود. فعلا تروریست‌ها در خانه‌هایی در کنار خیابان آزادی پنهان شده‌اند. در کنار خیابان آزادی $n$ خانه وجود دارد و در هر خانه **حداکثر یک** تروریست زندگی می‌کند. برای مهار این حمله‌ی تروریستی و دستگیری تروریست‌ها، $m$ پلیس آن خانه‌ها را زیر نظر گرفته‌اند. پلیس $i$-ام خانه‌های $l_i$ تا $r_i$ را زیر نظر گرفته‌است. می‌دانیم اگر در بازه‌ی تحت نظر یک پلیس بیش از یک تروریست زندگی کند، پلیس‌ها مشکوک شده و تروریست‌ها را دستگیر می‌کنند. مسریکس که از این ماجرا خبردار شده است، با خودش فکر می‌کند شاید بیشینه‌ی تعداد تروریست‌هایی که در این خانه‌ها می‌توانند زندگی کنند(بدون آن که دستگیر شوند) می‌تواند پارامتری موثّر در بحران محیط زیست باشد. پس از شما می‌خواهد که این مقدار را برای او محاسبه کنید. # ورودی در سطر اوّل ورودی به ترتیب دو عدد $n$ و $m$ می‌آید. در سطر $i$-ام از $m$ سطر بعد، دو عدد $l_i$ و $r_i$ آمده‌است که نشان‌دهنده‌ی بازه‌ی خانه‌هایی است که پلیس $i$-ام زیر نظر گرفته است. $$1 \le l_i \le r_i \le n$$ $$1 \le n, m \le 100\ 000$$ # خروجی در تنها سطر خروجی حداکثر تعداد تروریست‌هایی را چاپ کنید که می‌توانند در این خانه‌ها زندگی کنند و دستگیر نشوند. # مثال ## ورودی نمونه ۱ ``` 5 2 1 3 2 4 ``` ## خروجی نمونه ۱ ``` 3 ``` ## ورودی نمونه ۲ ``` 6 3 2 4 3 5 2 5 ``` ## خروجی نمونه ۲ ``` 3 ```

* محدودیت زمان:‌ ۱ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ------------------------------ به تعداد $ n $ بادکنک در یک ردیف قرار دارند. رنگ بادکنک $ i $ام $a_i$ است. در ابتدای هر روز همزمان بادکنک‌های هر دسته از بادکنک‌های پشت سر هم و هم رنگ که شامل حداقل ۳ بادکنک باشد می‌ترکند و در پایان هر روز بادکنک‌های باقی‌مانده دوباره در یک ردیفِ پیوسته با همان ترتیب قرار می‌گیرند. می‌خواهیم بدانیم هر بادکنک در چه روزی می‌ترکد. # ورودی در خط اول ورودی عدد $ n $ آمده است که تعداد بادکنک‌ها را نشان می‌دهد. $$1 \le n \le 300\ 000$$ $$1 \le a_i \le 10^9$$ # خروجی به ازای هر بادکنک روز ترکیدنش را چاپ کنید، اگر یک بادکنک هیچ‌گاه نمی‌ترکد `-1` را چاپ کنید. # مثال ## ورودی نمونه ``` 7 1 2 2 3 3 3 2 ``` ## خروجی نمونه ``` -1 2 2 1 1 1 2 ``` ## ورودی نمونه ``` 20 2 2 2 1 1 2 2 1 2 1 2 1 1 2 2 2 1 2 2 2 ``` ## خروجی نمونه ``` 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 2 2 1 1 1 2 1 1 1 ```