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

برنامه‌نویس‌های شرکت یکتانت به تعدادی تیم تقسیم شده‌اند و در یک صف کنار هم ایستاده‌اند. یک تیم، «همیشه حاضر» است، اگر و تنها اگر در بین هر $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$ ممکن برابر ۲ است.