- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
برنامهنویسهای شرکت یکتانت به تعدادی تیم تقسیم شدهاند و در یک صف کنار هم ایستادهاند. یک تیم، «همیشه حاضر» است، اگر و تنها اگر در بین هر \(k\) نفر متوالی از افراد داخل صف، حداقل یکی از افراد این تیم در بین این افراد باشد. کمترین مقدار \(k\) را بیابید که حداقل یک تیم «همیشه حاضر» داشته باشیم.
ورودی
در سطر اول ورودی، عدد صحیح \(n\) داده میشود که نشاندهندهی تعداد برنامهنویسهای شرکت یکتانت است. \[1 \le n \le 100\ 000\] در سطر دوم ورودی، شمارهی تیمهای این صف به ترتیب داده میشود که همگی اعداد طبیعی کمتر یا مساوی \(100\ 000\) است.
خروجی
کمترین مقدار \(k\) را بیابید که حداقل یک گروه همیشه حاضر داشته باشیم.
مثالها
ورودی نمونه ۱
6
1 2 3 1 3 1
خروجی نمونه ۱
3
در هر سه نفر متوالی، حداقل یک نفر از تیم ۱ وجود دارد. همچنین هیچ تیمی نیست که برای هر دو نفر متوالی در صف، یک نفر از آنها آمده باشد. بنابراین کمترین \(k\) ممکن برابر ۳ است.
ورودی نمونه ۲
3
1 2 3
خروجی نمونه ۲
2
از هر دو نفر متوالی، حداقل یک نفر از تیم ۲ وجود دارد. چنین خاصیتی برای هر نفر وجود ندارد. بنابراین کمترین \(k\) ممکن برابر ۲ است.