تیم همیشه حاضر


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

برنامه‌نویس‌های شرکت یکتانت به تعدادی تیم تقسیم شده‌اند و در یک صف کنار هم ایستاده‌اند. یک تیم، «همیشه حاضر» است، اگر و تنها اگر در بین هر kk نفر متوالی از افراد داخل صف، حداقل یکی از افراد این تیم در بین این افراد باشد. کمترین مقدار kk را بیابید که حداقل یک تیم «همیشه حاضر» داشته‌ باشیم.

ورودی🔗

در سطر اول ورودی، عدد صحیح nn داده می‌شود که نشان‌دهنده‌ی تعداد برنامه‌نویس‌های شرکت یکتانت است. 1n100 0001 \le n \le 100\ 000 در سطر دوم ورودی، شماره‌ی تیم‌های این صف به ترتیب داده می‌شود که همگی اعداد طبیعی کمتر یا مساوی 100 000100\ 000 است.

خروجی🔗

کم‌ترین مقدار kk را بیابید که حداقل یک گروه همیشه حاضر داشته باشیم.

مثال‌ها🔗

ورودی نمونه ۱🔗

6
1 2 3 1 3 1
Plain text

خروجی نمونه ۱🔗

3
Plain text

در هر سه نفر متوالی، حداقل یک نفر از تیم ۱ وجود دارد. همچنین هیچ تیمی نیست که برای هر دو نفر متوالی در صف، یک نفر از آن‌ها آمده باشد. بنابراین کم‌ترین kk ممکن برابر ۳ است.

ورودی نمونه ۲🔗

3
1 2 3
Plain text

خروجی نمونه ۲🔗

2
Plain text

از هر دو نفر متوالی، حداقل یک نفر از تیم ۲ وجود دارد. چنین خاصیتی برای هر نفر وجود ندارد. بنابراین کم‌ترین kk ممکن برابر ۲ است.