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

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

• $()$ یک پرانتزگذاری صحیح است.
• اگر $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