+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- کارلوس کِی‌روش در جام جهانی ۲۰۱۴ در تلاش برای پیدا کردن تاکتیکی برای بازی تیم ایران در مقابل آرژانتین بود. او یک تاکتیک را به صورت یک آرایه $n$ عضوی نشان می‌دهد که هر عضو آن عددی مثبت است و عضو $i$ ام این تاکتیک را به شکل $a_i$ نشان می‌دهیم. در یک تاکتیک، عضو $i$ ام آن را کلیدی می‌نامیم اگر به ازای هر $j$ کوچکتر از $i$ بدانیم عضو $i$ ام این تاکتیک از عضو $j$ ام آن بزرگتر است. به عبارتی عضو $i$ ام کلیدی است اگر و تنها اگر به ازای هر $j < i$ داشته باشیم $a_j < a_i$. حال میزان کارآمدی یک تاکتیک را تعداد اعضای کلیدی آن می‌نامیم. برای مثال کارآمدی تاکتیک $[2,5,1,10,10]$ برابر با $3$ است و عضو‌های اول، دوم و چهارم کلیدی اند. در آن زمان، یکی از دستیاران کارلوس کِی‌روش به او تاکتیک اولیه‌ای را پیشنهاد داد. اما کارلوس برای قوی‌تر کردن این تاکتیک، عملیات زیر را به تعداد دلخواه بر روی تاکتیک اولیه انجام داد: + او در هر عملیات می‌تواند دو عضو **مجاور** از آرایه تاکتیکش را انتخاب کند به طوری که **زوجیت این دو عضو برابر باشد** (یا هر دو زوج باشند، یا هر دو فرد باشند)، و سپس این دو عضو را با یکدیگر جابجا کند. به عنوان مثال در تاکتیک $[2,4,4,3]$ می‌توان اعضای اول و دوم آرایه که به ترتیب مقادیر 2 و 4 را دارند را جابجا کرد و به تاکتیک $[4,2,4,3]$ رسید. اما در تاکتیک $[2,3,5]$ نمی‌توان اعضای اول و دوم آرایه را جابجا کرد زیرا اعداد آنها 2 و 3 است که زوجیت برابر ندارند. یا به طور مثال در تاکتیک $[2,4,4,3]$ نمی‌توان اعضای اول و سوم را جابجا کرد زیرا با وجود برقرار بودن شرط برابری زوجیت، این دو عضو مجاور نیستند. او در نهایت بین تمام تاکتیک‌هایی که با عملیات بالا قابل رسیدن بودند، تاکتیکی با بیشترین میزان کارآمدی را به عنوان تاکتیک نهایی برای بازی انتخاب کرد. حال سال‌ها از آن ماجرا می‌گذرد و او میزان کارآمدی تاکتیک نهایی‌اش را فراموش کرده است و به دنبال این است که با داشتن تاکتیک اولیه، میزان کارآمدی تاکتیک نهایی‌اش را پیدا کند. به او کمک کنید تا این عدد را بیابید.  # ورودی ورودی شامل دو خط است که در خط اول عدد $n$، طول تاکتیک اولیه، و در خط بعدی $n$ عدد با فاصله می‌آیند که نشان‌دهنده یک آرایه $n$ عضوی (تاکتیک اولیه کارلوس کِی‌روش) است. $$ 1 \leq n \leq 3 \times 10^5 $$ $$ 0 \leq a_i \leq 10^9 $$ # خروجی خروجی برنامه یک خط است و در آن باید بیشترین میزان کارآمدی یک تاکتیک که کِی‌روش در آن زمان می‌توانست به آن برسد را خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 4 2 1 4 4 ``` ## خروجی نمونه ۱ ``` 2 ``` نیازی به تغییر وجود ندارد و کارآمدی این تاکتیک $2$ است. ## ورودی نمونه ۲ ``` 5 6 2 9 7 10 ``` ## خروجی نمونه ۲ ``` 5 ``` می‌توان با جا‌به‌جا کردن $6$ و $2$ و سپس جابه‌جا کردن $7$ و $9$، به تاکتیک $[2,6,7,9,10]$ رسید که کارآمدی آن $5$ است. ## ورودی نمونه ۳ ``` 5 8 18 6 7 2 ``` ## خروجی نمونه ۳ ``` 3 ```