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

آقای پستچی بترین پستچی دنیاست! با این حال او می‌خواهد روز‌های کاری مفیدی داشته باشد.

به او nn بسته‌ی پستی داده شده است که iiامین بسته را باید به خانه‌ی با کد پستی aia_i تحویل دهد. آقای پستچی عادت بدی دارد؛ در هر روز کاری او می‌تواند تعدادی بسته برداشته و به مقصد یکی از آن‌ها برود، آن را تحویل دهد و سپس به مقصدی برود که کدپستی‌اش دقیقا یکی بعد از کد پستی مقصد کنونی است! یعنی اگر کد پستی محلی که آقای پستچی بسته را تحویل داده برابر aia_i است، کد پستی بسته‌ی بعدی باید ai+1a_i+1 باشد. او آنقدر این‌کار را می‌کند تا بسته‌های همراهش تمام شوند و یا بسته‌ای با کد پستی بعدی همراه خود نبرده باشد.

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

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

برای مثال او همیشه می‌تواند بسته‌ها را در nn روز تحویل دهد، هر روز یک بسته. اما این بسیار عذاب وجدان آور است! ولی اگر کد پستی مقصد همه‌ی nn بسته یکسان باشد، آقای پستچی چاره‌ای جز این‌کار ندارد!

ورودی

در تنها سطر ورودی عدد nn آمده‌است که نمایانگر تعداد بسته‌های پستی می‌باشد.

سپس در سطر بعدی، nn عدد آمده‌است که عدد iiام نمایانگر aia_i می‌باشد. 0n1 0000 \le n \le 1\ 000 1ai10 0001 \le a_i \le 10\ 000

توجه کنید که ممکن است برای یک کد پستی، چند بسته در دست تحویل باشد. در این صورت هریک باید در روزی جداگانه تحویل داده شوند.

خروجی

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

مثال

ورودی نمونه ۱

10
1 2 3 4 5 10 9 8 7 6
Plain text

خروجی نمونه ۱

10
Plain text

در این نمونه آقای پستچی در یک روز می‌تواند همه‌ی ۱۰ بسته را تحویل دهد.

ورودی نمونه ۲

5
1 2 3 4 9
Plain text

خروجی نمونه ۲

1
Plain text

یک روش برای آقای پستچی تحویل بسته‌ به مقاصد ۱ و ۲ در اولین روز کاری و بسته به مقاصد ۳ و ۴ در دومین روز کاری و تحویل بسته با مقصد ۹ در روز سوم است.

ورودی نمونه ۳

0
Plain text

خروجی نمونه ۳

0
Plain text

این هم حالتی خاص که بسته‌ای وجود ندارد؛ کاملا هم منطقیست!

ورودی نمونه ۴

2
2 2
Plain text

خروجی نمونه ۴

1
Plain text

ارسال پاسخ برای این سؤال
فایلی انتخاب نشده است.