- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
آقای پستچی بترین پستچی دنیاست! با این حال او می‌خواهد روز‌های کاری مفیدی داشته باشد.
به او $n$ بسته‌ی پستی داده شده است که $i$امین بسته را باید به خانه‌ی با کد پستی $a_i$ تحویل دهد. آقای پستچی عادت بدی دارد؛ در هر روز کاری او می‌تواند تعدادی بسته برداشته و به مقصد یکی از آن‌ها برود، آن را تحویل دهد و سپس به مقصدی برود که کدپستی‌اش دقیقا یکی بعد از کد پستی مقصد کنونی است! یعنی اگر کد پستی محلی که آقای پستچی بسته را تحویل داده برابر $a_i$ است، کد پستی بسته‌ی بعدی باید $a_i+1$ باشد. او آنقدر این‌کار را میکند تا بسته‌های همراهش تمام شوند و یا بسته‌ای با کد پستی بعدی همراه خود نبرده باشد.
آقای پستچی می‌تواند این $n$ بسته را در تعداد دلخواهی روز و به ترتیبی دلخواه به مقصدشان تحویل دهد؛ تنها خواسته‌ی قلبی او این است که طوری کار کند که احساس کم‌کاری نکند. مثلا اگر روزی باشد که تنها یک بسته تحویل دهد، احساس کم‌کاری میکند و گریان به خانه بازمیگردد. اگر روزی دو بسته تحویل دهد، بسیار بهتر از روزهاییست که تنها یک بسته تحویل داده اما باز هم غم کم‌کاری و احساس گناه تمام وجودش را فرا می‌گیرد.
خلاصه آقای پستچی دنبال برنامه‌ای برای تحویل این $n$ بسته‌ی پستی است که کمترین تعداد بسته‌ای که در یک روز تحویل مشتری می‌دهد، بیشینه باشد.
برای مثال او همیشه می‌تواند بسته‌ها را در $n$ روز تحویل دهد، هر روز یک بسته. اما این بسیار عذاب وجدان آور است! ولی اگر کد پستی مقصد همه‌ی $n$ بسته یکسان باشد، آقای پستچی چاره‌ای جز این‌کار ندارد!
ورودی
در تنها سطر ورودی عدد $n$ آمده‌است که نمایانگر تعداد بسته‌های پستی می‌باشد.
سپس در سطر بعدی، $n$ عدد آمده‌است که عدد $i$ام نمایانگر $a_i$ می‌باشد. $$0 \le n \le 1\ 000 $$ $$1 \le a_i \le 10\ 000$$
توجه کنید که ممکن است برای یک کد پستی، چند بسته در دست تحویل باشد. در این صورت هریک باید در روزی جداگانه تحویل داده شوند.
خروجی
در تنها سطر خروجی یک عدد چاپ کنید که برابر بیشترین تعداد بسته‌ی ممکن است که آقای پستچی می‌تواند طوری بسته‌ها را تحویل دهد که در هر روز حداقل آن تعداد بسته را به دست صاحبش برساند.
مثال
ورودی نمونه ۱
10
1 2 3 4 5 10 9 8 7 6
خروجی نمونه ۱
10
در این نمونه آقای پستچی در یک روز می‌تواند همه‌ی ۱۰ بسته را تحویل دهد.
ورودی نمونه ۲
5
1 2 3 4 9
خروجی نمونه ۲
1
یک روش برای آقای پستچی تحویل بسته به مقاصد ۱ و ۲ در اولین روز کاری و بسته به مقاصد ۳ و ۴ در دومین روز کاری و تحویل بسته با مقصد ۹ در روز سوم است.
ورودی نمونه ۳
0
خروجی نمونه ۳
0
این هم حالتی خاص که بسته‌ای وجود ندارد؛ کاملا هم منطقیست!
ورودی نمونه ۴
2
2 2
خروجی نمونه ۴
1
ارسال پاسخ برای این سؤال