ماهان برای آینده‌ی خود برنامه‌ریزی اقتصادی کرده است و اکنون می‌داند در هر یک از $n$ روز آینده، چه مقدار پول احتیاج دارد. او می‌خواهد مخارج هر روزش را، صبح آن روز از پدر و یا مادرش به عنوان پول توجیبی بگیرد. ماهان دنباله‌ای به طول $n$ از مقدار پول‌هایی که می‌خواهد در روزهای آینده به‌دست آورد، تشکیل داده است که به آن دنباله‌ی ماهان می‌گوییم.
هریک از والدین ماهان مستقلا میزان پول توجیبی‌هایی که ماهان از او می‌گیرد را به صورت دنباله‌ای از اعداد ثبت می‌کند. هیچ یک از آن‌ها دوست ندارد مقدار پولی که ماهان از او می‌گیرد در مرور زمان روندی صعودی داشته باشد. به همین دلیل والدین، طول بلندترین زیردنباله‌ی صعودی در دنباله‌ی خود را محاسبه می‌کنند. دو عدد به‌دست آمده را عدد پدر و عدد مادر می‌گوییم. توجه کنید که دنباله‌ای صعودی، می‌تواند عناصر تکراری نیز داشته باشد.
ماهان دوست دارد عدد پدر و عدد مادر را کم کند. او به سرعت فهمید می‌تواند کاری کند که هر دوی این اعداد از سقف $\frac{L}{2}$ بیش‌تر نشود که $L$، طول بلندترین زیردنباله‌ی صعودی دنباله ماهان است.
به ماهان در انتخاب پدر یا مادر، برای گرفتن پول توجیبی در هر یک از $n$ روز پیش رو، کمک کنید. دقت کنید که عدد پدر و عدد مادر نباید از سقف $\frac{L}{2}$ بیش‌تر شود.
برنامه‌ای بنویسید که