مرتب سازی واگن
Problem
برای تعیین اینکه آیا می توان دنباله ای از اعداد را با استفاده از پشته مرتب کرد، لازم است.
یک قطار از مسیر 1 به بن بست رسیده است (تصویر را ببینید). می توان یک یا چند واگن اول را به طور همزمان از قطار جدا کرد و به بن بست رساند (در صورت تمایل حتی می توانید کل قطار را به یکباره به بن بست برسانید). پس از آن، تعدادی از واگن ها را به سمت مسیر 2 ببرید. سپس می توانید چند واگن دیگر را به بن بست بیاورید و دوباره بخشی از واگن ها را به سمت مسیر 2 منتقل کنید. و به همین ترتیب، به طوری که هر واگن از مسیر 1 به بن بست فقط یک بار رانندگی می کند و سپس یک بار از بن بست در مسیر 2 خارج می شود. ورود به بن بست از مسیر 2 یا خروج از بن بست در مسیر 1 ممنوع است. بدون وارد شدن به بن بست نمی توانید از مسیر 1 به مسیر 2 بروید.
مشخص است که واگن های قطار ابتدا به چه ترتیبی حرکت می کنند. لازم است با استفاده از عملیات ذکر شده، واگن های قطار به ترتیب حرکت کنند (اول اول، سپس دوم و غیره، از سر قطاری که در امتداد مسیر 2 دورتر از بن بست حرکت می کند). برنامه ای بنویسید تا مشخص شود آیا می توان آن را انجام داد.
ورودی
شماره N — تعداد واگن‌های قطار (\(1<=N<=2000\)). در مرحله بعدی شماره خودروها به ترتیب از سر قطاری است که در مسیر 1 به سمت بن بست حرکت می کند. ماشین‌ها با اعداد طبیعی از 1 تا N شماره‌گذاری می‌شوند که هر کدام دقیقاً یک بار اتفاق می‌افتد.
خروجی
آیا زمانی که قطار از بن بست مسیر شماره 2 را می گیرد، می توان واگن ها را به ترتیب از 1 به N، از سر قطار شمارش کرد؟ در صورت امکان، یک پیام YES نمایش دهید. اگر امکان پذیر نیست، NO را چاپ کنید.
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
یادداشت |
<بدن>
| 1 |
3
3 2 1
| بله |
باید کل قطار را به بن بست برسانیم و سپس آن را به طور کامل به مسیر دوم ببریم |
| 2 |
4
4 1 3 2
|
بله
|
ابتدا باید دو واگن را به بن بست بیاورید که یکی از آنها در بن بست رها می شود و دومی — به پیست 2 بروید، سپس دو اتومبیل دیگر را به بن بست بیاورید و 3 اتومبیل را که در بن بست ایستاده اند به مسیر 2 خارج کنید |
| 3 |
3
2 3 1
| نه |
|