+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فامیل دور که در کار در فعالیت دارد، از دیبی خواهش کرده است که یک شب به جای آی مجری برای بچه‌ها کتاب قصه بخواند. دیبی هم برای اینکه یک کتاب قصه بردارد، مجبور شد که یک کتاب قصه برندارد و به صورت رندم از بین کتاب‌های غیر قصه کتاب CLRS را انتخاب کرد. او شب کتاب را از آخر باز کرد تا برای بچه‌ها آن را از اول خوانده باشد! شاید برایتان عجیب باشد که آخر کتاب CLRS مبحث مرج سرت باشد اما در قصه‌ی این سوال که اینگونه است؛ پس دیبی شروع به خواندن مبحث مرج سرت کرد. خواندن مرج‌سرت دیبی اینقدر محیرالعقول بود که باعث شد که فامیل دور ایده‌ای برای بهتر کردن زمان مرج‌سرت به ذهنش برسد!! جیگر هم که معتقد است روش فامیل دور غلط است، به او یک آرایه $n$ تایی از اعداد داد که مرتب کند. روش فامیل دور برای مرتب کردن آرایه به این صورت است: او ابتدا قسمت‌های صعودی پشت سر هم آرایه را پیدا می‌کند و طول هر کدام را روی کاغذ می‌نویسد. برای مثال اگر آرایه $ 1, 3, 5, 4, 6$ باشد، قسمت‌های صعودی پشت سر هم آرایه دو تا است: $ 1, 3, 5$ و $ 4, 6$ که طول اولی ۳ و دومی ۲ می‌باشد. پس فامیل دور دو عدد ۳ و ۲ را روی کاغذ می‌نویسد. او $k$ عدد روی کاغذ می‌نویسد. سپس اینگونه شروع به مرتب کردن آرایه می‌کند که هر دفعه دو قسمت صعودی مجاور از آرایه را انتخاب می‌کند و آن‌ها را شبیه مرج سرت مرج می‌کند؛ یعنی اینکه بعد از این کار این دو قسمت صعودی تبدیل به یک قسمت صعودی می‌شوند. به عبارت دیگر او این دو قسمت را به یک قسمت مرتب شده تبدیل می‌کند. سپس دو عدد مربوط به این دو قسمت را از روی کاغذ پاک می‌کند و اندازه‌ی قسمت جدید را جای این دو عدد روی کاغذ می‌نویسد. همچنین او برای مرج کردن دو قسمت پشت سر هم به اندازه‌ی مجموع اندازه‌شان (یعنی مجموع اعدادی که روی کاغذ برای این دو قسمت نوشته بود) باید زمان صرف کند. حالا فامیل دور برای اینکه کَلِ جیگر را بخواباند می‌خواهد در سریعترین زمان ممکن آرایه را مرتب کرده و به جیگر تحویل دهد. چون او از قصه‌ی دیبی به شدت خوابش گرفته است، شما به او بگویید که این کمترین زمان چقدر است. # ورودی در سطر اول ورودی دو عدد $n$ و $k$‌ آمده است. سپس در سطر بعدی $k$ عدد می‌آید که $i$ امین عدد نمایانگر $i$ امین عددی است که فامیل دور روی کاغذ نوشته است. $$ 1 \le n \le 10^9 $$ $$ 1 \le k \le 100 $$ تضمین می‌شود که جمع اعداد آمده در سطر دوم ورودی برابر $n$ می‌باشد و همچنین همه‌شان اعدادی طبیعی بین ۱ تا $n$ می‌باشند. # خروجی در تنها سطر خروجی کمترین زمان برای مرتب کردن آرایه را خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 10 3 1 3 6 ``` ## خروجی نمونه ۱ ``` 14 ``` توضیح نمونه‌ی ۱: روش بهینه این است که ابتدا دو قسمت اول را با هم یکی کنیم و سپس دو قسمت به وجود آمده را با هم یک قسمت کنیم. هزینه‌ی مرج اول ۴ و هزینه‌ی مرج دوم ۱۰ می‌باشد که در مجموع ۱۴ می‌شود. ## ورودی نمونه ۲ ``` 7 4 1 1 1 4 ``` ## خروجی نمونه ۲ ``` 12 ``` ## ورودی نمونه ۳ ``` 2 2 1 1 ``` ## خروجی نمونه ۳ ``` 2 ``` ## ورودی نمونه ۴ ``` 4 3 1 2 1 ``` ## خروجی نمونه ۴ ``` 7 ```

حل سؤال در بانک سؤالات