Stack

یک ماشین پشته‌ای شامل یک شمارنده، یک پشته و یک صفحه‌ی نمایش است. یک برنامه دنباله‌ای از دو دستور زیر است:

• دستور Push: این دستور به مقدار شمارنده یک واحد اضافه می‌کند و سپس مقدار جدید شمارنده را به روی پشته اضافه می کند.
• دستور Pop: این دستور بالاترین عدد ذخیره شده در پشته را از پشته حذف و در صفحه‌ی نمایش چاپ می‌کند. اگر پشته خالی باشد این دستور قانونی نمی‌باشد و ماشین خراب می‌شود.

در ابتدای اجرای هر برنامه، پشته و صفحه‌ی نمایش ماشین خالی هستند و مقدار شمارنده برابر صفر است.

جایگشتی از اعداد ۱ تا $n$ داده شده است. برنامه‌ای به زبان این ماشین بنویسید که (بدون خراب شدن) در صفحه‌ی نمایش خود، این جایگشت را چاپ کند.

• در سطر اول ورودی عدد $n$ ($n \leq 10^5$) آمده است.
• در سطر بعد $n$ عدد آمده‌اند که نمایش دهنده‌ی جایگشتی هستند که قرار است در صفحه‌ی نمایش ماشین چاپ شود.

• در صورتی که این‌کار امکان‌پذیر نیست، در تنها سطر خروجی عدد $-1$ را چاپ کنید.
• در غیر این صورت، در یک سطر دستورات برنامه را بنویسید. به ازای هر دستور یکی از دو حرف U و P را چاپ کنید. U نشان‌دهنده‌ی Push و P نشان‌دهنده‌ی Pop است.

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

• سوال بعد
• سوال قبل