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

---

دانشجویی یک رشته از پرانتزها پیدا کرده است. او می‌داند یک پرانتزگذاری درست به شکل زیر است:

• \(()\) یک پرانتزگذاری صحیح است.
• اگر \(S\) یک پرانتزگذاری صحیح باشد، \((S)\) هم یک پرانتزگذاری درست است.
• اگر \(S\) و \(T\) یک پرانتزگذاری درست باشد، \(TS\) که از کنار هم گذاشتن آن دو رشته به دست می‌آید نیز پرانتزگذاری صحیح است.

همچنین یک شیفت دوری به اندازه‌ی \(k\) روی رشته‌ی \(S\) باعث تبدیل شدن آن به رشته‌ی \(T\) می‌شود که داریم: \[\forall \,0 \leq i \lt |S|, \quad T[i] = S[(i + k) mod |S|]\]

خوشحالی دانشجو برابر تعداد \(k\)های کوچکتر از طول رشته ورودی است که شیفت های دوری رشته پیدا شده به اندازه \(k\)، پرانتزگذاری درست باشد. این تعداد را پیدا کرده و به دانشجو اعلام کنید تا آن مقدار خوشحال شود.

ورودی

در خط اول ورودی عدد \(n\) که طول رشته است آمده است. در خط دوم ورودی رشته‌ی \(S\) شامل کاراکتر های ) و ( است می‌آید.

خروجی

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

مثال‌ها

ورودی نمونه ۱

6
))()((

خروجی نمونه ۱

2

ورودی نمونه ۲

6
())(((

خروجی نمونه ۲

0