فهرست مندرجات
ماهان برای آینده‌ی خود برنامه‌ریزی اقتصادی کرده است و اکنون می‌داند در هر یک از $n$ روز آینده، چه مقدار پول احتیاج دارد. او می‌خواهد مخارج هر روزش را، صبح آن روز از پدر و یا مادرش به عنوان پول توجیبی بگیرد. ماهان دنباله‌ای به طول $n$ از مقدار پول‌هایی که می‌خواهد در روزهای آینده به‌دست آورد، تشکیل داده است که به آن دنباله‌ی ماهان می‌گوییم.
هریک از والدین ماهان مستقلا میزان پول توجیبی‌هایی که ماهان از او می‌گیرد را به صورت دنباله‌ای از اعداد ثبت می‌کند. هیچ یک از آن‌ها دوست ندارد مقدار پولی که ماهان از او می‌گیرد در مرور زمان روندی صعودی داشته باشد. به همین دلیل والدین، طول بلندترین زیردنباله‌ی صعودی در دنباله‌ی خود را محاسبه می‌کنند. دو عدد به‌دست آمده را عدد پدر و عدد مادر می‌گوییم. توجه کنید که دنباله‌ای صعودی، می‌تواند عناصر تکراری نیز داشته باشد.
ماهان دوست دارد عدد پدر و عدد مادر را کم کند. او به سرعت فهمید می‌تواند کاری کند که هر دوی این اعداد از سقف $\frac{L}{2}$ بیش‌تر نشود که $L$، طول بلندترین زیردنباله‌ی صعودی دنباله ماهان است.
به ماهان در انتخاب پدر یا مادر، برای گرفتن پول توجیبی در هر یک از $n$ روز پیش رو، کمک کنید. دقت کنید که عدد پدر و عدد مادر نباید از سقف $\frac{L}{2}$ بیش‌تر شود.
برنامه‌ای بنویسید که
- دنباله مقدار پول‌هایی را که در $n$ روز آینده باید گرفته شود، از ورودی بخواند؛
- این $n$ روز را به دو مجموعه با شرایط گفته شده افراز کند؛
- این دو مجموعه را در خروجی بنویسد.
ورودی
- در سطر اول ورودی، عدد $n$ قرار دارد.
- در سطر دوم ورودی، $n$ عدد صحیح نامنفی قرار دارد که با یک فاصله‌ی خالی از هم جدا شده‌اند.
- عدد $i$ام، میزان پول توجیبی‌ای است که ماهان می‌خواهد در روز $i$ام از یکی از والدینش بگیرد.
- $1 \leq n \leq 100000$.
- در نیمی از تست‌ها $n \leq 10000$ است.
خروجی
- در سطر اول خروجی، تعداد روزهایی را بنویسید که ماهان باید از مادرش پول توجیبی بگیرد.
- در سطر دوم خروجی، شماره این روزها را به ترتیب صعودی با یک فاصله از هم بنویسید.
- در سطر سوم خروجی، تعداد روزهایی را بنویسید که ماهان باید از پدرش پول توجیبی بگیرد.
- در سطر چهارم خروجی، شماره این روزها را به ترتیب صعودی با یک فاصله از هم بنویسید.
محدودیت‌ها
- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
ورودی و خروجی نمونه
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
