ﻣﺎﻫﺎﻥ ﺑﺮﺍﯼ ﺁﯾﻨﺪه‌ی ﺧﻮﺩ ﺑﺮﻧﺎﻣﻪﺭﯾﺰﯼ ﺍﻗﺘﺼﺎﺩﯼ ﮐﺮﺩﻩ ﺍﺳﺖ ﻭ ﺍﮐﻨﻮﻥ ﻣﯽﺩﺍﻧﺪ ﺩﺭ ﻫﺮ ﯾﮏ ﺍﺯ $n$ ﺭﻭﺯ ﺁﯾﻨﺪﻩ، ﭼﻪ ﻣﻘﺪﺍﺭ ﭘﻮﻝ ﺍﺣﺘﯿﺎﺝ ﺩﺍﺭﺩ. ﺍﻭ ﻣﯽﺧﻮﺍﻫﺪ ﻣﺨﺎﺭﺝ ﻫﺮ ﺭﻭﺯﺵ ﺭﺍ، ﺻﺒﺢ ﺁﻥ ﺭﻭﺯ ﺍﺯ ﭘﺪﺭ ﻭ ﯾﺎ ﻣﺎﺩﺭﺵ ﺑﻪ ﻋﻨﻮﺍﻥ ﭘﻮﻝ ﺗﻮﺟﯿﺒﯽ ﺑﮕﯿﺮﺩ. ﻣﺎﻫﺎﻥ ﺩﻧﺒﺎﻟﻪﺍﯼ ﺑﻪ ﻃﻮﻝ $n$ ﺍﺯ ﻣﻘﺪﺍﺭ ﭘﻮﻟﻬﺎﯾﯽ ﮐﻪ ﻣﯽﺧﻮﺍﻫﺪ ﺩﺭ ﺭﻭﺯﻫﺎﯼ ﺁﯾﻨﺪﻩ ﺑﺪﺳﺖ ﺁﻭﺭﺩ، ﺗﺸﮑﯿﻞ ﺩﺍﺩﻩ ﺍﺳﺖ ﮐﻪ ﺑﻪ ﺁﻥ «دنباله‌ی ﻣﺎﻫﺎﻥ» ﻣﯽﮔﻮﯾﯿﻢ.

ﻫﺮ ﯾﮏ ﺍﺯ ﻭﺍﻟﺪﯾﻦ ﻣﺎﻫﺎﻥ ﻣﺴﺘﻘﻼً ﻣﯿﺰﺍﻥ ﭘﻮﻝ ﺗﻮﺟﯿﺒﯽﻫﺎﯾﯽ ﮐﻪ ﻣﺎﻫﺎﻥ ﺍﺯ ﺍﻭ ﻣﯽﮔﯿﺮﺩ ﺭﺍ ﺑﻪ ﺻﻮﺭﺕ ﺩﻧﺒﺎﻟﻪﺍﯼ ﺍﺯ ﺍﻋﺪﺍﺩ ﺛﺒﺖ ﻣﯽﮐﻨﺪ. ﻫﯿﭻ ﯾﮏ ﺍﺯ ﺁن‌ها ﺩﻭﺳﺖ ﻧﺪﺍﺭﺩ ﻣﻘﺪﺍﺭ ﭘﻮﻟﯽ ﮐﻪ ﻣﺎﻫﺎﻥ ﺍﺯ ﺍﻭ ﻣﯽﮔﯿﺮﺩ ﺩﺭ ﻣﺮﻭﺭ ﺯﻣﺎﻥ ﺭﻭﻧﺪﯼ ﺻﻌﻮﺩﯼ ﺩﺍﺷﺘﻪ ﺑﺎﺷﺪ. ﺑﻪ ﻫﻤﯿﻦ ﺩﻟﯿﻞ ﻭﺍﻟﺪﯾﻦ، ﻃﻮﻝ ﺑﻠﻨﺪﺗﺮﯾﻦ زیردنباله‌ی ﺻﻌﻮﺩﯼ ﺩﺭ ﺩﻧﺒﺎﻟﻪﯼ ﺧﻮﺩ ﺭﺍ ﻣﺤﺎﺳﺒﻪ ﻣﯽﮐﻨﻨﺪ. ﺩﻭ ﻋﺪﺩ ﺑﻪ ﺩﺳﺖ ﺁﻣﺪﻩ ﺭﺍ «ﻋﺪﺩ ﭘﺪﺭ» ﻭ «ﻋﺪﺩ ﻣﺎﺩﺭ» ﻣﯽﮔﻮﯾﯿﻢ. ﺗﻮﺟﻪ ﮐﻨﯿﺪ ﮐﻪ ﺩﻧﺒﺎﻟﻪﺍﯼ ﺻﻌﻮﺩﯼ، ﻣﯽﺗﻮﺍﻧﺪ ﻋﻨﺎﺻﺮ ﺗﮑﺮﺍﺭﯼ ﻧﯿﺰ ﺩﺍﺷﺘﻪ ﺑﺎﺷﺪ.

ﻣﺎﻫﺎﻥ ﺩﻭﺳﺖ ﺩﺍﺭﺩ «ﻋﺪﺩ ﭘﺪﺭ» ﻭ «ﻋﺪﺩ ﻣﺎﺩﺭ» ﺭﺍ ﮐﻢ ﮐﻨﺪ. ﺍﻭ ﺑﻪ ﺳﺮﻋﺖ ﻓﻬﻤﯿﺪ ﻣﯽﺗﻮﺍﻧﺪ ﮐﺎﺭﯼ ﮐﻨﺪ ﮐ‰ﻪ ﻫ‰ﺮ ﺩﻭﯼ ﺍﯾ‰ﻦ ﺍﻋ‰ﺪﺍﺩ ﺍﺯ $\lceil \frac{L}{2} \rceil$ بیش‌تر ﻧ‰ﺸ‰ﻮﺩ ﮐ‰ﻪ $L$، ﻃ‰ﻮﻝ ﺑ‰ﻠ‰ﻨ‰ﺪﺗ‰ﺮﯾ‰ﻦ ﺯﯾ‰ﺮﺩنباله‌ی صعودی دنباله‌ی ماهان است.

ﺑﻪ ﻣﺎﻫﺎﻥ ﺩﺭ ﺍﻧﺘﺨﺎﺏ ﭘﺪﺭ ﯾﺎ ﻣﺎﺩﺭ، ﺑﺮﺍﯼ ﮔﺮﻓﺘﻦ ﭘﻮﻝﺗﻮﺟﯿﺒﯽ ﺩﺭ ﻫﺮ ﯾﮏ ﺍﺯ $n$ روز پیش رو، کمک کنید. دقت کنید که عدد پدر و عدد مادر نباید از $\lceil \frac{L}{2} \rceil$ بیش‌تر شود.

ﺑﺮﻧﺎﻣﻪﺍﯼ ﺑﻨﻮﯾﺴﯿﺪ ﮐﻪ:

• دنباله‌ی مقدار پول‌هایی را که در $n$ روز آینده باید گرفته شود، از ورودی بخواند.
• این $n$ روز را به دو مجموعه با شرایط گفته شده افراز کند.
• این دو مجموعه را در خروجی بنویسد.

• ﺩﺭ ﺳﻄﺮ ﺍﻭﻝ ﻭﺭﻭﺩﯼ، ﻋﺪﺩ $n$ قرار دارد.( $1\leq n \leq 10^5$)
• در سطر دوم ورودی، $n$ ﻋﺪﺩ ﺻﺤﯿﺢ ﻧﺎﻣﻨﻔﯽ ﻗﺮﺍﺭ ﺩﺍﺭﺩ ﮐﻪ ﺑﺎ ﯾﮏ فاصله‌ی ﺧﺎﻟﯽ ﺍﺯ ﻫﻢ ﺟﺪﺍ ﺷﺪﻩﺍﻧﺪ. عدد $i$ام، میزان پول تو جیبی‌ای است که ماهان می‌خواهد در روز $i$ام از یکی از والدینش بگیرد.

• ﺩﺭ ﺳﻄﺮ ﺍﻭﻝ ﺧﺮﻭﺟﯽ، ﺗﻌﺪﺍﺩ ﺭﻭﺯﻫﺎﯾﯽ ﺭﺍ ﺑﻨﻮﯾﺴﯿﺪ ﮐﻪ ﻣﺎﻫﺎﻥ ﺑﺎﯾﺪ ﺍﺯ ﻣﺎﺩﺭﺵ ﭘﻮﻝ ﺗﻮﺟﯿﺒﯽ ﺑﮕﯿﺮﺩ.
• ﺩﺭ ﺳﻄﺮ ﺩﻭﻡ ﺧﺮﻭﺟﯽ، ﺷﻤﺎﺭه‌ی این روزها را به ﺗﺮﺗﯿﺐ ﺻﻌﻮﺩﯼ ﺑﺎ ﯾﮏ ﻓﺎﺻﻠﻪ ﺍﺯ ﻫﻢ ﺑﻨﻮﯾﺴﯿﺪ.
• ﺩﺭ ﺳﻄﺮ ﺳﻮﻡ ﺧﺮﻭﺟﯽ، ﺗﻌﺪﺍﺩ ﺭﻭﺯﻫﺎﯾﯽ ﺭﺍ ﺑﻨﻮﯾﺴﯿﺪ ﮐﻪ ﻣﺎﻫﺎﻥ ﺑﺎﯾﺪ ﺍﺯ ﭘﺪﺭﺵ ﭘﻮﻝ ﺗﻮﺟﯿﺒﯽ ﺑﮕﯿﺮﺩ.
• ﺩﺭ ﺳﻄﺮ ﭼﻬﺎﺭﻡ ﺧﺮﻭﺟﯽ، ﺷﻤﺎﺭه‌ی ﺍﯾﻦ ﺭﻭﺯﻫﺎ ﺭﺍ ﺑﻪ ﺗﺮﺗﯿﺐ ﺻﻌﻮﺩﯼ ﺑﺎ ﯾﮏ ﻓﺎﺻﻠﻪ ﺍﺯ ﻫﻢ ﺑﻨﻮﯾﺴﯿﺪ.

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

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