چیدمان


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

عمو که فردی بسیار پول‌پرست است، به چیدن سکه‌هایش روی هم علاقه‌مند است.

عمو سکه‌هایش را روی یک خط بصورت nn ستون از سکه با ارتفاع برابر چیده است. عمو هرشب قبل از خواب ستون‌های سکه‌اش را برانداز میکند. او دیشب قبل از خواب متوجه‌شد که چیدمان سکه‌ها به‌هم خورده است. عمو پس از تحقیق متوجه‌شد که کریم، یک پسر‌بچه‌ی ۵ ساله‌ که به جابجایی سکه‌ها علاقه‌مند است، تعدادی سکه از هر ستون به ستون‌های دیگر منتقل کرده است.

حال عمو میخواهد بار دیگر ستون‌هایش را هم ارتفاع کند. او بدلیل خواب‌آلودگی، در هر دقیقه میتواند یک سکه از روی یکی از ستون ها برداشته و روی ستون دیگری بگذارد. با داشتن ارتفاع سکه‌ها بگویید که این مرتب سازی حداقل چند دقیقه از او وقت خواهد گرفت.

ورودی🔗

سطر اول ورودی شامل عدد nn است که نمایانگر تعداد ستون‌های سکه‌ی عمو است. در سطر iiم از هریک از nn سطر بعدی یک عدد طبیعی حداقل ۰ و حداکثر 10410^4 آمده است که ارتفاع ستون‌ها را نشان میدهد. تضمین میشود که عمو میتواند با حرکت گفته‌شده همه ستون‌ها را هم ارتفاع کند.

1n1041 \le n \le 10^4

خروجی🔗

در تنها سطر خروجی یک عدد چاپ کنید که برابر کمینه دقایقیست که عمو میتواند در آن ستون‌هایش را هم ارتفاع کند.

ورودی نمونه🔗

4
1
2
3
6
Plain text

خروجی نمونه🔗

3
Plain text

عمو میتواند یک سکه از ستون آخر به ستون دوم ببرد و ۲ سکه از ستون آخر به ستون اول تا ارتفاع همه‌ی ستون‌ها برابر ۳ شود.